String Permutation - Fast Algorithm ?

[vsha041]

Hi,

I have written an inefficient program for string matching. In this program we are suppose to tell whether it is possible to have all possible permutations of the first string (all distinct characters) within the second string (does not have to be continuos). The input is two strings. For example:-

first string - abc
second string - abacaba

Now we need to see if all 6 permutations of the first string "abc" are there within "abacaba" or not ? In this case the answer is YES, because

1. ab_c___ (abc)
2. a__c_b_ (acb)
3. _bac___ (bac)
4. _b_ca__ (bca)
5. ___cab_ (cab)
6. ___c_ba (cba)

The program which I have written works for smaller strings because I am generating all permutations one by one and checking iteratvely if they exist within the second string or not ? My program does not work for large first string length like 10 or 15. For example: 15 ! is around 13 trillion. This means we need to check all 13 trillion permutations if they exist or not within the second string.


I have attached my program. It accepts a number first which tells the length of first string. Input of 3 means abc , 5 means abcde, input of 7 means, input string is abcdefgh. This means, first input cannot be more than 26. The second input is the string itself (abacaba in the above example), inside which all the combinations have to be tested.

Thanks

Varun

[D_Drmmr]

This means we need to check all 13 trillion permutations if they exist or not within the second string.

Even with your approach, you only have to check all permutations if all of them 'exist' in the second string. If you find only one permutation that doesn't exist, you're done.

Seems to me that the approach breaks down into a tree. From the root node, you branch into three nodes: one representing all permutations with a first, one with b first, one with c first. I'll let you fill in the rest.

Then you can adapt your search strategy based on whether you expect the answer to be yes or no. In the latter case, you could e.g. start with the letter that occurs the latest in the second string, thereby reducing the probability that the permutation 'exists' in the second string.