4
$\begingroup$

I came across this algorithm in a book, and have been struggling to understand the basic idea. The books says it uses backtracking to print all possible permutations of the characters in a string. In Python, the algorithm is given as:

def bitStr(n, s):
    if n == 1: return s
    return [digit + bits for digit in bitStr(1, s) for bits in bitStr(n - 1, s)]

print(bitStr(3, 'abc'))

I'm pretty weak in algorithmic thinking and am struggling for both an intuitive understanding of this, as well as tracing it. Can somebody explain what this algorithm does and how exactly is uses 'backtracking'?

Improve this question
$\endgroup$
6
  • $\begingroup$ Do you understand the backtracking as such? Or you don't understand how to use the backtracking to generate permutations? $\endgroup$ – fade2black Aug 19 '17 at 17:20
  • $\begingroup$ @fade2black I've read the definition of backtracking (solving smaller problems first and abandoning the approaches that don't work) but I don't see how that applies here. This is the first time I've encountered backtracking and you can say I'm not familiar with it. :D $\endgroup$ – ankush981 Aug 19 '17 at 17:27
  • $\begingroup$ @fade2black I also just now traced it on paper and it looks like a typical two-term recursion. Nothing "backtracking" about it as far as I can tell. $\endgroup$ – ankush981 Aug 19 '17 at 17:31
  • $\begingroup$ Can you replace the code by pseudocode for the benefit of those of us who can't read python? $\endgroup$ – Yuval Filmus Aug 20 '17 at 12:47
  • $\begingroup$ As an aside, this should be implemented as an iterator in python. $\endgroup$ – Yuval Filmus Aug 20 '17 at 12:48
6
$\begingroup$

Backtracking is a general algorithm "that incrementally builds candidates to the solutions, and abandons each partial candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution." (Wikipedia).

So, basically, what you do is build incrementally all permutations. As soon as as you build a single permutation, you backtrack and build another one, and so on until you generate all $n!$ possible permutations, say, on $n$ symbols.

Example: $n=3$, $S=\{1,2,3\}$.

You start with $1$. Then you move forward an choose $2$ (since $1$ has already been chosen), and then you choose $3$. At that point you have built the first permutation $123$. Then you backtrack and select $3$ instead of $2$, then select $2$, and you have $132$. You backtrack again, but you have already used $2$ and $3$, so you backtrack again (one level up where), and choose $2$ instead of $1$, then you select $1$, and finally $3$, so you have $213$.
The following picture should clarify the basic idea:

enter image description here

In other words, you simply traverse the tree, and when you reach the leaf you print the permutation. Then you backtrack one level up, and try another option. Moving one level up the tree is what we call the backtracking in this case.

As for implementation, the backtracking is usually implemented using recursive call(s) as in your example. I assume that you have necessary programming skills to implement this basic idea yourself, in particular solving problems using recursive calls.

Improve this answer
$\endgroup$
5
  • $\begingroup$ The code in question doesn't actually generate all permutations, since it allows repetition. $\endgroup$ – Yuval Filmus Aug 20 '17 at 12:49
  • $\begingroup$ @YuvalFilmus do you mean the Python code in the OP? $\endgroup$ – fade2black Aug 20 '17 at 12:51
  • $\begingroup$ Yes. The code doesn't generate the recursion tree in your answer. $\endgroup$ – Yuval Filmus Aug 20 '17 at 12:52
  • 1
    $\begingroup$ @YuvalFilmus maybe. You know we dont consider here source codes in a spesific programming language. So I didn't bother to analyze the source code. It seems the asker has problem with solving generating permutations using bactracking rather than coding it. $\endgroup$ – fade2black Aug 20 '17 at 13:00
  • $\begingroup$ Could you clarify your use of the term "backtrack"? From the Wikipedia quotation, the algorithm "backtracks" as soon as it determines that the candidate cannot possibly be completed to a valid solution. But in your example, you mentioned that we backtrack after 123. But 123 is a valid solution, and it is confusing to me how backtracking applies to this problem. $\endgroup$ – Sung Cho Apr 10 '20 at 2:25
0
$\begingroup$

Suppose that we have an alphabet $\Sigma$. Let $\Sigma^n$ denote all words of length $n$ over $\Sigma$. We can define $\Sigma^n$ inductively (for $n \geq 1$) as follows: $$ \Sigma^1 = \Sigma, \quad \Sigma^n = \{ \sigma w : \sigma \in \Sigma, w \in \Sigma^{n-1} \}. $$ This is exactly what you code is doing.

For example, running the procedure on $\Sigma = \{a,b,c\}$ and $n = 1$ will generate the set $\{a,b,c\}$. Running it with $n = 2$ will generate all concatenations of a symbol from $\Sigma$ and a word in $\Sigma^1 = \{a,b,c\}$. Running in with $n = 3$ will generate all concatenations of a symbol from $\Sigma$ and a word in $\Sigma^2 = \{aa,ab,ac,ba,bb,bc,ca,cb,cc\}$. And so on.

The given code generates these combinations in a specific order, but deciphering depends on specific features of the syntax of python.

As an aside, the word permutation has a different meaning in mathematics, which you can look up on Wikipedia or in discrete mathematics textbooks.

Improve this answer
$\endgroup$
7
  • $\begingroup$ So, are they permutations on 'abc'? I wouldn't say this code generates permutations, does it? $\endgroup$ – fade2black Aug 20 '17 at 13:26
  • $\begingroup$ The permutations of abc are described in your answer. The code does something else. $\endgroup$ – Yuval Filmus Aug 20 '17 at 13:30
  • $\begingroup$ What I am concerned about is either the code is wrong or the asker interpreted the code wrongly and it has nothing to do with the permutations. $\endgroup$ – fade2black Aug 20 '17 at 13:33
  • $\begingroup$ Here is the output of the code: ['aaa', 'aab', 'aac', 'aba', 'abb', 'abc', 'aca', 'acb', 'acc', 'baa', 'bab', 'bac', 'bba', 'bbb', 'bbc', 'bca', 'bcb', 'bcc', 'caa', 'cab', 'cac', 'cba', 'cbb', 'cbc', 'cca', 'ccb', 'ccc']. $\endgroup$ – Yuval Filmus Aug 20 '17 at 13:34
  • $\begingroup$ Yes, you are right. I misused the term 'permutation'. But I'm curious as to what the output should be called? Combination? Of course not. :D $\endgroup$ – ankush981 Aug 20 '17 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.