Find The Hidden List

[nikolas]

Hello everyone,

i recently encountered a logic problem which is this:

There is a list(original) that contains all numbers from 1...n, without duplicates and not necessary in order. We dont know that list but we know

5 other lists which are the result of the original in that way: The first list came from moving one number from the original list to another position( be careful, move not exchange),

the second list came from moving another different number from the original list. What actions you must do to find the original list?

for example: 5 lists={[1,2,5,3,4],[1,5,3,4,2],[4,2,1,5,3],[2,3,1,5,4],[2,1,3,4,5]} and the original is Original=[2,1,5,3,4].

[bonanova]

Line up the lists and inspect contiguous groups of three columns.

There should be one and only one element that appears in each line of that nx3 array.

That element occupies the middle column in the original array.

Exception: the element might appear on every line of the nx3 array except one:

that is the list in which it was the moved element.

Example: in the five lists above:

The element 1 appears in the 123 positions in every case. That places it in position 2.

The element 5 appears in the 234 positions in every case. That places it in position 3

The element 5 appears in the 345 position with one exception. That places it in position 4.

[fabpig]

I'm assuming that the number of lists given is always n?

Superb puzzle, nikolas

[nikolas]

@fabpig the numer of elements each list contains is n(variable). In this case n=5, and n>=3 always because of the number of permutations. e.g. for n=2, n!=1*2=2<5, but 3!=1*2*3=6>5 and as a result we can have the 5 lists.

[nikolas]

@bananova good thinking but here where you say

The element 5 appears in the 234 positions in every case. That places it in position 3

in positions 234 in line 5 element 5 is missing, and so does element 3 in line 4 in position 345.

and here:

The element 5 appears in the 345 position with one exception. That places it in position 4.

you should be meaning element 3(because 3 is in position 3) but in the 4th list in positions 123 there is no element 3

[fabpig]

@fabpig the numer of elements each list contains is n(variable). In this case n=5, and n>=3 always because of the number of permutations. e.g. for n=2, n!=1*2=2<5, but 3!=1*2*3=6>5 and as a result we can have the 5 lists.

Not sure if that's what I'm asking . If there are eg. 9 elements, will there be 9 lists (that way, we know that each element has been moved once)?

[nikolas]

@fabpig Ohh i see, no there will be only 5 lists!

Hint: its 5 lists and only no matter how many elements you have, number 5 plays a role!

[fabpig]

The number in position 1 must always be in either position 1 or 2 in every list apart from the list in which it's moved. If this applies to only one number, then that must be pos 1.
Now, it's possible that more than one number meets this criterion (for example if list 3 was [2,1,4,5,3] and/or list 4 was [2,1,3,5,4] then both "2" and "1" fall into this category). In this case we need to check the order in which the two numbers occur more than once. Whichever occurs first (more than once) is pos 1.

Similarly, the number in position 5 must always be in position 4 or 5 apart from the list in which it's moved.

I suspect that the same procedure can be applied to positions 2 onwards (+-1 of actual position), but I've yet to try it exhaustively.

[BMAD]

for example: 5 lists={[1,2,5,3,4],[1,5,3,4,2],[4,2,1,5,3],[2,3,1,5,4],[2,1,3,4,5]} and the original is Original=[2,1,5,3,4].

I understand that to go from [1,2,5,3,4] to [1,5,3,4,2] can be easily achieved by moving the 2 to the rear but how does one then go to [4,2,1,5,3]? Can we slide two numbers at once?

[BMAD]

also, is it that we can't move the same number consecutively or is it that we can't do the same number more than once?

[fabpig]

for example: 5 lists={[1,2,5,3,4],[1,5,3,4,2],[4,2,1,5,3],[2,3,1,5,4],[2,1,3,4,5]} and the original is Original=[2,1,5,3,4].

I understand that to go from [1,2,5,3,4] to [1,5,3,4,2] can be easily achieved by moving the 2 to the rear but how does one then go to [4,2,1,5,3]? Can we slide two numbers at once?

Think I can answer that.....

Each list has one number moved from the original list...not the previous list.

[BMAD]

That makes sense! Thank you.

[phil1882]

man look tough.

it seems to me though bonanova is on the right track.

take the five lists look at numbers either in the same position, or in the same order.

that will tell you the original order.

I'm not entirely sure why 5 is the magic number though.

lets say we have 9 numbers.

4 1 7 8 2 3 5 9 6

2 4 1 9 7 8 3 5 6

2 4 1 8 3 5 7 9 6

2 4 1 6 7 8 3 5 9

3 2 4 1 7 8 5 9 6

can you deduce my original sequence?

[BMAD]

man look tough.

it seems to me though bonanova is on the right track.

take the five lists look at numbers either in the same position, or in the same order.

that will tell you the original order.

I'm not entirely sure why 5 is the magic number though.

lets say we have 9 numbers.

4 1 7 8 2 3 5 9 6

2 4 1 9 7 8 3 5 6

2 4 1 8 3 5 7 9 6

2 4 1 6 7 8 3 5 9

3 2 4 1 7 8 5 9 6

can you deduce my original sequence?

Looks like whatever the mode of each value behind another assigned value

@phill 2,4,1,3,7,8,5,9,6

since 4 most commonly followed 2; 4 is behind 2. since 1 is most commonly behind 4, 1 is behind 4. and so on.

[fabpig]

Bad wording... I said that whichever number came first in the lists, when I meant whichever number came to the left of the other one - not necessarily immediately left of - (more than once)

But even the "more than once" is wrong. EG. take original list 1,2,3,4,5 for simplicity's sake. It is possible for the following 5 lists:

2,1,3,4,5 /* Here "1" has moved to column 2 */
2,1,3,4,5 /* And "2" has moved to column 1! */
1,2,3,5,4
1,2,4,3,5
1,3,2,4,5

In the above, the occupant of column 1 in the original must occupy columns 1 or 2 in the 5 lists on at least 4 occasions. That applies to "1" and "2". 2 comes left of 1 twice, vs 1 left of 2, 3 times. So it's whichever is the leftmost more often that determines that number 1 has column 1 (in this example). This could be nikolas's reference to the number 5 (majority 3 to 2).

So. Lets move on to column 2. It's possible for the inmate to occupy columns 1,2, or 3 in the 5 lists on >= (n - 1) occasions in the 3 columns. Any occurence of number "1" can be ignored as it has already been allocated to column 1. There are 5 occurences of "2" , and 4 occurences of "3" in the 3 columns. As 2 precedes 3 in the 5 lists on more occasions, it can be allocated to column 2.

Same applies to each subsequent column, ignoring numbers that have already been allocated.

Think That about covers it.

I'm going to try to write a program to see if it works for lists with more elements (you have been warned )

This could get (even) ugli(er)!

[BMAD]

Fair point. Shoot. Thought I solved one.

[plasmid]

You are given five lists. For any two numbers in the series, call them A and B, you will know that in one of those lists A has been moved, in one other list B has been moved, and in three lists neither A nor B was the number that was moved -- meaning that in those three lists A will be to the left of B only if it's to the left of B in the original list, and to the right of B only if it's to the right of B in the original list.

So if you find three (or more) lists where A is to the left of B, then you know that A is to the left of B in the original list. If you find three (or more) where A is to the right of B, then A must be to the right of B in the original list.

Repeat that for all pairs of numbers (or howevermany you need to figure out the list's order).

This would be the reason why having (at least) five lists, regardless of how long the list of numbers is, is important.

Edited February 27, 2014 by plasmid

[fabpig]

You are given five lists. For any two numbers in the series, call them A and B, you will know that in one of those lists A has been moved, in one other list B has been moved, and in three lists neither A nor B was the number that was moved -- meaning that in those three lists A will be to the left of B only if it's to the left of B in the original list, and to the right of B only if it's to the right of B in the original list.

So if you find three (or more) lists where A is to the left of B, then you know that A is to the left of B in the original list. If you find three (or more) where A is to the right of B, then A must be to the right of B in the original list.

Repeat that for all pairs of numbers (or howevermany you need to figure out the list's order).

This would be the reason why having (at least) five lists, regardless of how long the list of numbers is, is important.

That's what I thought I was saying.

Damn my northern accent!

[fabpig]

man look tough.

it seems to me though bonanova is on the right track.

take the five lists look at numbers either in the same position, or in the same order.

that will tell you the original order.

I'm not entirely sure why 5 is the magic number though.

lets say we have 9 numbers.

4 1 7 8 2 3 5 9 6

2 4 1 9 7 8 3 5 6

2 4 1 8 3 5 7 9 6

2 4 1 6 7 8 3 5 9

3 2 4 1 7 8 5 9 6

can you deduce my original sequence?

2,4,1,7,8,3,5,9,6

woohoo

[plasmid]

Ah, right you are fabpig. Your post two above mine does seem to say what I was saying, I just hadn't completely followed it.

[nikolas]

many gredits to all of you and fabpig!