1

Possible Duplicate:
Generating all Possible Combinations

I want to generate all possible unique patterns for a string which will include all of its characters including duplicate characters, if any.

For example:

string: abc
patterns: abc acb bca bac cab cba

string: abb
patterns: abb bab bba

Also, is there a formula to state how many unique patterns can be created of a string to verify the validity of the algorithm? So far, I have tried multiple approaches, but turned out to be not reliable as the number of character increases.

Community
  • 1
  • 1
user1857001
  • 19
  • 2
  • You are looking for permutations: http://en.wikipedia.org/wiki/Permutations – emartel Nov 27 '12 at 15:31
  • 2
    You're talking about permutations, take a look here: http://en.wikipedia.org/wiki/Permutation. You will find a way to count them and also many approaches in generating them. – Jack Nov 27 '12 at 15:31
  • @emartel and jack – thanks to both of you for pointing me to this. Looks to be what I want. – user1857001 Nov 27 '12 at 15:40

4 Answers4

1

You can try something like this:-

  using System;

  namespace ConsoleApplication3
 {
    class Permute
    {
             private void swap (ref char a, ref char b)
             {
                    if(a==b)return;
                    a^=b;
                    b^=a;
                    a^=b;
              }

              public void setper(char[] list)
              {
                    int x=list.Length-1;
                    go(list,0,x);
              }

              private void go (char[] list, int k, int m)
              {
                    int i;
                    if (k == m)
                       {
                             Console.Write (list);
                             Console.WriteLine (" ");
                        }
                    else
                         for (i = k; i <= m; i++)
                        {
                               swap (ref list[k],ref list[i]);
                               go (list, k+1, m);
                               swap (ref list[k],ref list[i]);
                        }
               }
     }

     class Class1
    {
           static void Main()
           {

                  Permute p = new Permute();
                  string c="sagiv";
                   char []c2=c.ToCharArray ();
                   /*calling the permute*/
                  p.setper(c2);
              }
       }
  }
Rahul Tripathi
  • 168,305
  • 31
  • 280
  • 331
  • Nice solution! However it can not work properly where there is duplicate elements! Take the string "abb" as an example. It will output "abb" for two times! – Chasefornone Nov 27 '12 at 16:36
0

If you start with your data sorted, you can use repeated calls of std::next_permutation to cycle through all permutations. std::next_permutation handles the case with repeated elements, like your abb string, without problems.

user515430
  • 3,341
  • 2
  • 17
  • 13
0

My idea is similar with Rahul Tripathi's, however I did a tricky thing to make it work properly for duplicate elements. Anytime before we do a swap operation, we look back to check whether this element has show up before. If it is a duplicate element, we should not do the swap operation.The code is below with c++:

#include<iostream>

using namespace std;

bool isDupilicate(char input[],int start,int j)
{
     bool ret=false;
     for(int i=start;i<j;++i)
     {
             if(input[i]==input[j])
             {
                ret=true;
                break;
             }
     }
     return ret;
}

void swap(char& a,char &b)
{
     char temp=a;
     a=b;
     b=temp;
}

void permutation(char input[],int start,int length)
{
       if(start==length)
       {
           for(int i=0;i<length;++i)cout<<input[i];
           cout<<endl;
       }
       else 
       {
           for(int i=start;i<length;++i)
           {
                   if(isDupilicate(input,start,i))continue;
                   swap(input[i],input[start]);
                   permutation(input,start+1,length);
                   swap(input[i],input[start]);

           } 
       }          
}

int main()
{
    cout<<"Input for abb"<<endl;
    char input[3]={'a','b','b'};
    permutation(input,0,3);
    cout<<"________________"<<endl;

    cout<<"Input for abc"<<endl;
    input[2]='c';
    permutation(input,0,3);

    getchar();
    getchar();

}

Check this link to figure out how many unique patterns can be created! Hope it helps!

Chasefornone
  • 747
  • 1
  • 7
  • 15
-2

To calculate unique permutations it's simply length of word (e.g 3) to the power of possible characters. so if it was all lower-case characters and the word length is 3 it's 3^26=2541865828329 (26 because that's the number of lower-case characters in the english alphabet) combinations.

You can calculate all possible combinations using recursion.

Daniel Lane
  • 2,575
  • 2
  • 18
  • 33