<commit_before>---
layout: post
title: Brute force, Backtracking and SymPy - counting permutations with no repeated letters
---

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script>

There are 12 unique permutations of the word 'food'. Of these, there are only six that satisfy the constraint that no adjacent letters are equal:

- fodo
- odof
- odfo
- ofdo
- ofod
- dofo

How can we efficiently *count* the number of such permutations for a given word?

## Approach 1: Brute Force

The simplest approach is to generate each and every possible permutation of the word in turn, checking whether any adjacent letters are equal, and incrementing the count if not.

The following code uses Python's itertools module to generate the permutations (and also to simplify the process of checking for repeated letters):

```python
import itertools

def length(iterable):
    """
    Length of an iterable (but not necessarily Sized) object.
    """
    return sum(1 for _ in iterable)

def has_equal_adjacent_letters(string):
    """
    Indicate whether string has adjacent letters which are equal:

      toot -> True
      yoyo -> False

    """
    return any(length(letters) > 1 for _, letters in itertools.groupby(string))

def approach_1(string):
    """
    Count the permuations of string that have no repeated letters
    by generating all permutations and checking them one by one.
    """
    all_permuations = itertools.permutations(string)
    # keep track of unique permutations using a set
    unique_perms = set(perm for perm in all_permuations if not has_equal_adjacent_letters(perm))
    return len(unique_perms)
```

For the word 'food' this works nicely:

```python
>>> approach_1('food')
6
```

However, we're in trouble if our word is much longer. As you may be aware, the number of (not necessarily unique) permutations of a word of length $n$ is
<commit_msg>Simplify code for approach 1<commit_after>---
layout: post
title: Brute force, Backtracking and SymPy - counting permutations with no repeated letters
---

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script>

There are 12 unique permutations of the word 'food'. Of these, there are only six that satisfy the constraint that no adjacent letters are equal:

- fodo
- odof
- odfo
- ofdo
- ofod
- dofo

How can we efficiently *count* the number of such permutations for a given word?

## Approach 1: Brute Force

The simplest approach is to generate each and every possible permutation of the word in turn, checking whether any adjacent letters are equal, and incrementing the count if not.

The following code uses Python's itertools module to generate the permutations (and also to simplify the process of checking for repeated letters):

```python
from itertools import permutations, groupby, filterfalse

def length(iterable):
    """
    Length of an iterable (but not necessarily Sized) object.
    """
    return sum(1 for _ in iterable)

def has_equal_adjacent_letters(string):
    """
    Indicate whether string has adjacent letters which are equal:

      toot -> True
      yoyo -> False

    """
    return any(length(letters) > 1 for _, letters in groupby(string))

def approach_1(string):
    """
    Count the permuations of string that have no repeated letters
    by generating all permutations and checking them one by one.
    """
    wanted_perms = filterfalse(has_equal_adjacent_letters, permutations(string))
    # keep track of unique permutations using a set
    unique_perms = set(wanted_perms)
    return len(unique_perms)
```

For the word 'food' this works nicely:

```python
>>> approach_1('food')
6
```

However, we're in trouble if our word is much longer. As you may be aware, the number of (not necessarily unique) permutations of a word of length $n$ is

{'fraction_non_alphanumeric': 0.09558308015891563, 'fraction_numerical': 0.005842486562280907, 'mean_word_length': 3.7928331466965286, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 23, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6426575', 'n_tokens_mistral': 1299, 'n_tokens_neox': 1212, 'n_words': 500}