Determine the original sequence

Write a program that will determine the original sequence given five variations. The original sequence will be contain n unique elements in any order. A variation is made by making a copy of the original sequence and choosing a random item from the copy and inserting it at any random location in the sequence (this could be the same index it was originally at). Also, each item can only be chosen once so that the five variations will each operate on a different item.

Input

``````5          # number of items
1 2 3 4 5  # unknown
2 1 3 4 5  # 3,4,5 candidate
3 1 2 4 5  # 4,5 candidate
4 1 2 3 5  # 1,2 candidate
5 1 2 3 4  # 1,2,3 candidate
# 1,2,3 + 3,4,5 = 1,2,3,4,5
``````

Output

``````1 2 3 4 5
``````

In case it's not clear what I meant, here is Python code to generate an example

``````from random import shuffle,randint

n = 5 # can be any number
a = range(1, n+1)
shuffle(a)
s = set()
#print str(a[0])+"".join(" "+str(x) for x in a[1:]) #debug (print orig sequence)
for run in xrange(5):
c = list(a)
i = randint(0, n-1)
while c[i] in s:
i = randint(0, n-1)
t = c.pop(i)
c.insert(randint(0, n-1), t)
print str(c[0])+"".join(" "+str(x) for x in c[1:])
``````

Keep in mind, the numbers aren't necessarily consecutive or all positive. The shortest wins.

Longer Example

Here's how the five variations are generated. Each is just one step away from the original.

``````6 3 4 5 7 1 2 # original

6 4 5 7 3 1 2 # 3 moved to index 3
3 6 4 5 7 1 2 # 6 moved to index 1
6 3 4 5 1 2 7 # 7 moved to index 6
6 3 4 7 1 5 2 # 5 moved to index 5
6 3 2 4 5 7 1 # 2 moved to index 2
``````

Contiguous subsequences of the original will remain in each variation.

``````6 4 5 7 3 1 2
3 6 4 5 7 1 2
x x # (1, 2) is a candidate

6 4 5 7 3 1 2
6 3 4 5 1 2 7
x             # (6) is a candidate but we can ignore it since one item
# doesn't tell us much

6 4 5 7 3 1 2
6 3 4 7 1 5 2
x     x     x

6 4 5 7 3 1 2
6 3 2 4 5 7 1
x

3 6 4 5 7 1 2
6 3 4 5 1 2 7
x x       # (4, 5)

3 6 4 5 7 1 2
6 3 4 7 1 5 2
x

3 6 4 5 7 1 2
6 3 2 4 5 7 1

6 3 4 5 1 2 7
6 3 4 7 1 5 2
x x x         # (6, 3, 4)

6 3 4 5 1 2 7
6 3 2 4 5 7 1
x x           # (6, 3)

6 3 4 7 1 5 2
6 3 2 4 5 7 1
x x           # (6, 3)
``````

Merging the candidates together we realize the sequence has

``````(6, 3, 4, 5) and (1, 2)
``````

We can get the rest by realizing that by inserting an item, the sequence may be shifted by one in either direction, so repeat the above except using a unshifted sequence.

``````4 5 7 3 1 2
3 6 4 5 7 1 2

4 5 7 3 1 2
6 3 4 5 1 2 7
x x   # (1, 2)

4 5 7 3 1 2
6 3 4 7 1 5 2
x

4 5 7 3 1 2
6 3 2 4 5 7 1

6 4 5 7 1 2
6 3 4 5 1 2 7
x       x x   # (1, 2)

6 4 5 7 1 2
6 3 4 7 1 5 2
x     x x     # (7, 1) something new!

6 4 5 7 1 2
6 3 2 4 5 7 1
x

3 4 5 1 2 7
6 3 4 7 1 5 2

3 4 5 1 2 7
6 3 2 4 5 7 1
x

3 4 7 1 5 2
6 3 2 4 5 7 1
x
``````

Merging those with our previous results give us

``````(6, 3, 4, 5) and (7, 1, 2)
``````

Now do the same again except unshifting the other.

``````6 4 5 7 3 1 2
6 4 5 7 1 2
x x x x       # (6, 4, 5, 7)

6 4 5 7 3 1 2
3 4 5 1 2 7
x x         # (4, 5)

6 4 5 7 3 1 2
3 4 7 1 5 2
x

6 4 5 7 3 1 2
3 2 4 5 7 1

3 6 4 5 7 1 2
3 4 5 1 2 7
x

3 6 4 5 7 1 2
3 4 7 1 5 2
x

3 6 4 5 7 1 2
3 2 4 5 7 1
x   x x x x   # (4, 5, 7, 1)

6 3 4 5 1 2 7
3 4 7 1 5 2

6 3 4 5 1 2 7
3 2 4 5 7 1
x x       # (4, 5)

6 3 4 7 1 5 2
3 2 4 5 7 1
x
``````

Merging those with our previous gives us

``````(6, 3, 4, 5, 7, 1, 2)
``````

Each candidate gives the "general" order of the original sequence. For example (6, 4, 5, 7) just says "6 before 4 before 5 before 7" but doesn't say anything about numbers that max exist between say 6 and 4. However, we have (6, 3, 4, 5) which lets us know a 3 exists between 6 and 4 so when we merge the two candidates, we end up with (6, 3, 4, 5, 7).

Input

``````6 1 7 2 5 3 4
1 7 2 5 6 3 4
1 7 5 6 3 4 2
1 7 2 6 5 3 4
7 2 5 6 1 3 4
``````

Output

``````1 7 2 5 6 3 4
``````

Doing it similar to the above, we get candidates

``````(3, 4)
(5, 3, 4)
(1, 7)
(1, 7, 2)
(5, 6)
(1, 7, 2, 5)
(6, 3, 4)
(7, 2, 5, 6)
(7, 2)
``````

Some are obviously self-contained, so simplifying we get

``````(5, 3, 4)
(1, 7, 2, 5)
(6, 3, 4)
(7, 2, 5, 6)
``````

Then one is an obvious extension of the other, so we get

``````(1, 7, 2, 5, 6)
(5, 3, 4)
(6, 3, 4)
``````

The first lets us know 5 goes before 6 and the other two say (3, 4) go after both 5 and 6, so we get

``````(1, 7, 2, 5, 6, 3, 4)
``````

If you noticed, each of the items in a candidate can represent a vertex and an edge going from one item to another. Putting them all together will allow you to make a DAG. This is just the way I do it, there may be other and better ways to do it.

-
I don't get it. You take out a number at a certain place an put it back in at another. But what do the 'candidates' mean? – Nippey Oct 26 '12 at 10:08
The candidates are what I refer to as contiguous subsequences of the original sequence. You know that since at most one element is moved (to a different position or possibly the same), you can just find candidates and piece it together. That's what I tried to demonstrate in the example. – miles Oct 27 '12 at 0:35
after the longer explanation i feel even more confused – ardnew Oct 27 '12 at 2:01
D: oh my am I really that bad at explaining things – miles Oct 27 '12 at 2:26

GolfScript, 44 characters

``````n/{~]}%:^0=.,{{{.3\$?\2\$?>}^%\$2={\}*}*]}*" "*
``````

The solution can be tested online.

The algorithm is based on the fact, that the order in which two items can be may be reversed mostly twice: once when the first item is moved and once when the second is. Thus, in at least 3 out of the five cases the original order is preserved.

``````n/          # Split the input into lines
{~]}%       # and evaluate each line.
:^          # We now have an array of arrays
# which we save to variable ^
0=          # Take the first item of this list
.,{{        # We now sort this list of items using bubble-sort
# The following lines calculate the comparator
{       #   For each line in the input
.3\$?  #     Determine position of first item
\2\$?  #     Determine position of second item
>     #     Is first before/after second?
}^%     #   End for each
\$2=     #   Take the middle element of the list.
#   (i.e. was first item most of the time
#   positioned after the second)
{\}*    #   Swap if it was the case.
}*]}*       # End of bubble-sort loops
" "*        # Format output
``````
-
Novel idea, and it works for many cases, but in a few cases, it gives the incorrect sequence. Example (6 1 7 2 5 3 4), (1 7 2 5 6 3 4), (1 7 5 6 3 4 2), (1 7 2 6 5 3 4), and (7 2 5 6 1 3 4) where the original is (1 7 2 5 6 3 4). +1 – miles Oct 28 '12 at 22:42
@milest It does not show incorrect results; for your example see here. – Howard Oct 29 '12 at 5:51
You're correct, it does not, but it seems when I copied/pasted, it left a trailing newline which altered the results as in this – miles Oct 29 '12 at 5:55
@milest Ah, you're correct. It sometimes doesn't work if you have trailing newlines. If you have proper input it works perfectly. – Howard Oct 29 '12 at 6:08
Great job using a solution I would never have thought of! – miles Nov 4 '12 at 20:45