An algorithm to find a permutation in sequence

Question

I'm asking for a simple problem: how to find one (and only one) permutation in a sequence of numbers (with repetitions) with the lowest complexity?

Suppose we have the sequence: 1 1 2 3 4. Then we permute 2 and 3, so we have: 1 1 3 2 4. How can I find that 2 and 3 have been permuted? The worst solution would be to generate all possibilities and compare each one with original permuted sequence, but I need something fast...

Thank you for your answer.

• st0le: I frankly don't understand the question. Are you looking for minimum swaps you need to get from sequence 1 to sequence 2?
• David J: You can compare if the elements itself and the amount of the elements is the same.
• wildplasser: Generate all the permutations you want to detect (in your example there are only 8, IICC) and generate a DFA for it. (f)lex is your friend.

Answer 1

The problem with this is there will be multiple solutions to your problem without some constraints such as the order is sequentially found.

What I'd look at is first test that there are still the same values in the sequence and if so just step through one by one until a mismatch is found and then find where the first occurance of the other value is and mark that as the permutation. Now continue searching for the next modification and so on...

If you just want to know how much it's changed I'd look at levenshtein algorithm. The basis of this algorithm may even give you what you need for your own custom algorithm or inspire other approaches.

This is fast but it won't tell you which items have changed.

The only full solution I know of would be to record each change as it happens so you can just look at the history of changes to know the perfect answer.

Answer 2

function findswaps:
 linkedlist old <- store old string in linkedlist
 linkedlist new <- store new string in linkedlist
 compare elements one by one:
 if same
 next iteration until exhausted
 else
 remember old item
 iterate through future `new` elements one by one:
 if old item is found
 report its position in new list
 else
 error

My humble attempt please correct me if wrong, so I can help better. I'm guessing the data is unordered so it can't be any faster than linear?

Answer 3

If there is only 1 swap between the original and derived arrays, you could try something like this at O(n) for array length n:

int count = 0;
int[] mismatches;
foreach index in array {
 if original[index] != derived[index] {
 if count == 2 {
 fail
 }
 mismatches[count++] = index;
 }
}
if count == 2 and
 original[mismatches[0]] == derived[mismatches[1]] and
 original[mismatches[1]] == derived[mismatches[0]] {
 succeed
}
fail

Note that this reports a fail when nothing was swapped between the arrays.