18

I am learning backtracking and recursion and I am stuck at an algorithm for printing all the permutations of a string. I solved it using the bell algorithm for permutation but I am not able to understand the recursion method. I searched the web and found this code:

void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); 
       }
   }
}

How is this algorithm basically working I am unable to understand? I even tried dry running!

How is the backtracking applied?

And is it more efficient than the Bell Algorithm for calculation of permutation?

4

8 に答える 8

24

アルゴリズムは基本的に次のロジックで機能します。

文字列 X のすべての順列は、その文字を含まない文字列 X のすべての順列と組み合わせた、X 内の可能な各文字のすべての順列と同じです。

つまり、「abcd」の順列はすべて

  • 「bcd」のすべての順列と連結された「a」
  • 「acd」のすべての順列と連結された「b」
  • 「悪い」のすべての順列と連結された「c」
  • 「bca」のすべての順列と連結された「d」

このアルゴリズムは特に、部分文字列で再帰を実行する代わりに、入力文字列で再帰を実行し、部分文字列を割り当てるために追加のメモリを消費しません。「バックトラック」は、文字列への変更を元に戻し、元の状態のままにします。

于 2013-06-07T17:28:03.853 に答える
5

再帰はそれを本当に単純化します:

public static void permutation(String str) 
{ 
    permutation("", str); 
}

private static void permutation(String prefix, String str) 
{
    int n = str.length();
    if (n == 0) {
        System.out.println(prefix);
    } else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}
于 2014-02-18T10:21:46.937 に答える
1 
I create more specific but not efficient Program for permutation for general string.
It's work nice way.
//ubuntu 13.10 and g++ compiler but it's works on any platform and OS
//All Permutation of general string.

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
using namespace std;
int len;
string str;

void permutation(int cnum)
{
    int mid;
    int flag=1;
    int giga=0;
    int dead=0;
    int array[50];
    for(int i=0;i<len-1;i++)
    {
        array[50]='\0';
        dead=0;
        for(int j=cnum;j<len+cnum;j++)
        {
            mid=j%len;
            if(mid==cnum && flag==1)
            {
                cout<<str[mid];
                array[dead]=mid;
                dead++;
                flag=0;
            }
                else
            {
                giga=(i+j)%len;
                for(int k=0;k<dead;k++)                 
                {
                    if((array[k]==giga) && flag==0)
                    {
                    giga=(giga+1)%len;
                    }
                }
                cout<<str[giga];
                array[dead]=giga;
                dead++;

            }
        }
        cout<<endl;
        flag=1; 
    }
}
int main()
{
    cout<<"Enter the string :: ";
    getline(cin,str);
    len=str.length();
    cout<<"String length = "<<len<<endl;
    cout<<"Total permutation = "<<len*(len-1)<<endl;
    for(int j=0;j<len;j++)
    {
        permutation(j);
    }
return 0;
}
于 2014-10-09T19:21:22.633 に答える
0 
def perms(s):
    if len(s) < 1:
        return [s]
    ps = []
    for i in range(0, len(s)):
        head, tail = s[i], s[0:i] + s[i + 1:]
        ps.extend([head + tailp for tailp in perms(tail)])
    return ps
于 2016-11-13T22:40:36.523 に答える