current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.
up vote 1 down vote favorite

I have a sequence of permutations formed using these strings: "A", "BC" and "D". The permutations are:

BCAD
ABCD
BCDA
DABC
ADBC
DBCA

Now I need to reverse engineer this; i.e. I have a text file containing the sequences, I should be able to tell the strings that are used to construct the permutations. What algorithm I can use?

share|improve this question

closed as unclear what you're asking by MichaelT, Dan Pichelman, GlenH7, Robert Harvey, gnat Jul 27 '14 at 19:34

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.
    
Do you always get all n! permutations to work with, or just some? –  Kilian Foth Jul 23 '14 at 14:25
    
All permutations should work with. –  Inam Ul Haq Jul 23 '14 at 14:34
    
Would the source strings "AB", "CD" produce the same set of permutations as "A", "BC", "D"? If no, how will they differ? –  kdgregory Jul 23 '14 at 17:08
    
(and if yes, they produce the same permutations, then you have your answer) –  kdgregory Jul 23 '14 at 17:09
    
Nope here "A", "BD" "D" are different sets so they will only produce 3! = 6 permutations. "BC" is a single element. –  Inam Ul Haq Jul 23 '14 at 17:31

2 Answers 2

up vote 2 down vote

This is related to the Longest common substring problem and can be solved using a Generalized suffix tree.

Use Ukkonen's algorithm to Build a tree (not a binary tree), adding nodes as you parse the file. Ukkonen's algorithm works in O(n) (linear) time, for constant-size alphabets, and O(n log n) in general.

The leaf nodes of the tree can then be traversed to obtain the original sequences.

share|improve this answer
up vote 0 down vote

Going by your example and assuming each character is expected to be unique, a simple algorithm could be:

// Grab the first character of each line
    // If it hasn't been encountered before, add to a collection
// Examine the first permutation
    // Read each character into a string until a match is found in your collection
    // Store the found string
    // Repeat
share|improve this answer

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