1

I am looking at the backtracking algorithm for computing permutations, and although I can understand what is happening, I cannot understand how it solves the problem for any value of h elements.

How are proofs that algorithm is correct made. Can one show that by swapping, one gets all possible arrangements ? Is there any mathematical book about recursion ?

Can anyone explain to me a proof that leads to the backtracking algorithm ?

Here is the algorithm in C++ using a string to play scrabble.

To run an example of all permutations call permute ("abc" 0 3) 

void permute(string& a, int i, int h)
 {
  if (i == h)
    cout << a << endl;
  else {
    for (int j = i; j < h; j++) {
      swap(a[i], a[j]);     // Swapping done
      permute(a, i + 1, l); // Recursion called
      swap(a[i], a[j]);     // backtrack
  }}}

When i=h this will generate

abc acb bac bca cab cba

Now, let's do permute ("abcd" 0 4). Now things really become complicated. Although I have done the example, understood the backtracking procedure, and that one gets all possible permutation of letters, I find difficulty starting on a proof of correctness.

Veak
  • 177
  • 6
  • 1
    This question is too general for an answer here. The usual way to prove a recursive algorithm correct is by structural induction. https://en.wikipedia.org/wiki/Structural_induction. Try seaching for structural induction permutations and combinations – Ethan Bolker Jul 31 '23 at 20:38
  • What algorithm are you talking about? – Rob Arthan Jul 31 '23 at 20:44
  • Had a look at structural induction but without much idea about what I have to do for this case. Would need help about how to approach this algorithm and that it produces all permutations. Any ideas would be much welcomed. – Veak Jul 31 '23 at 21:02
  • What kind of things need I learn to check such algorithms. I do not think that it is a very difficult algorithm but have not come up with anything to start with. – Veak Jul 31 '23 at 21:11
  • Your code isn't right. The loop condition should be $\mathtt{j < l}$. When you have fixed that, try to to come up with a description of what the $i$ parameter means: executing some test runs on simple examples may help. Once you understand that, you will be much closer to finding an inductive proof of correctness. – Rob Arthan Jul 31 '23 at 21:32
  • You are quite right. I have done all that, and also completed the case of permute ("abcd" 0 4). I understand the backtracking procedure. Am done with examples, but have problem starting about an inductive proof. That it works for all cases of general length h. – Veak Jul 31 '23 at 21:37
  • i indicates the depth level. When the deepest level is reached, we spit out a one of the 4! possibilities. – Veak Jul 31 '23 at 21:51
  • That's not a good description of how it works. Try stepping through a call like $\mathtt{permute("abcd", 2, 4")}$. – Rob Arthan Jul 31 '23 at 21:59
  • The elements preceeding i are left untouched. I also get to "abcd" again. Which gets all permutations from index i onwards. – Veak Jul 31 '23 at 23:10
  • Doing the Base Case is easy. Prove that the algorithm works correctly for the smallest possible input, a string with only one letter. But I am struggling with the Inductive Step. Showing that if the algorithm works correctly for words of length h, it also works correctly for words of length h+1. This involves showing that the algorithm generates all permutations for a word of length h+1 and does not produce duplicates or miss any valid permutations. – Veak Aug 01 '23 at 04:47

0 Answers0