Printable View
Hello,
i'm searching for a algorithm for the following problem. I want to combine every number in a list with each one of the List except for itself and none of the numbers should be repeat more than two times in a row. The list can be randomly long.
For example
1,2,3,4
The result should be:
1-2
2-3
3-4
1-4
1-3
4-2
Can you help me? Thanks in advance!
Regards
Bluescreen
You can represent the pairs in a table like this.
For example the upper left x represents the 1,2 pair.Code:1 2 3 4
1 x x x
2 x x
3 x
4
Now the problems is to visit the x in a sequence that obeys the non-repetition rule. For example you did it like this,
I claim (without proof) that there's a systematic visiting order that always obeys the rule. This is when you move diagonally back and forth along ever smaller diagonals like (I put in an extra number to make the system more visible),Code:1 2 3 4
1 1 5 4
2 2 6
3 3
4
And this is the corresponding list,Code:1 2 3 4 5
1 1 7 8 10
2 2 6 9
3 3 5
4 4
5
1,2
2,3
3,4
4,5
3,5
2,4
1,3
1.4
2,5
1,5
In my previous post I gave an algorithm without proof. I've been thinking about one and it goes like this:
Say i,j is a pair in a matrix generated by the algorithm. This is the example matrix from my previous post but it can be arbitrarily big.
It's given that j>i. This can be restated as j=i+n where n>0.Code:1 2 3 4 5
1 1 7 8 10
2 2 6 9
3 3 5
4 4
5
The idea behind the proof is to check every possible subsequence consisting of three successive pairs and make sure that it obeys the non-repetition rule. This rule states that if a number is present in both the two first pairs of a 3-sequence it must not be present in the third pair. If this holds for any 3-sequence it holds for the full sequence as a whole.
There are six distinctly different 3-sequence cases to check. One case is down a diagonal (example 1,2,3) and another is up a diagonal (example 5,6,7). Then there are two cases when a down diagonal turns up; First when it enters the turn (example 3,4,5) and then when it exits the turn (example 4,5,6). And finally there are two corresponding cases when an up diagonal enters and exits a down turn (example 6,7,8 and 7,8,9).
Lets start with a down diagonal. We have an arbitrary pair i,j in any down diagonal and its two successor pairs in the same diagonal,
i, j
i+1, j+1 (diagonally down)
i+2, j+2 (diagonally down)
We know that j=i+n where n>0 so we can do,
i, i+n
i+1, i+n+1
i+2, i+n+2
Inspection tells us that the only possible way for a number in the first pair to equal one in the second is when i+n of the first equals i+1 of the second. This happens when n=1. All other lead to contradictions.
Now can i+1 be equal to any of the two numbers in the third pair? No because i+1 can never be i+2 and it can never be i+n+2 (not for any n>0 and then obviously not for n=1). So these are are contradictions and the conclussion is that the non-repetition rule holds in every down diagonal 3-sequence.
Now the remaining five cases must be checked in a similar way. Lets take the one when a down diagonal enters an up turn. We have,
i, j
i+1, j+1 (diagonally down)
i, j+1 (straight up)
Utilizing j=i+n gives
i, i+n
i+1, i+n+1
i, i+n+1
Again the only case when a number can be present in the two first pairs is when i+n equals i+1, that is when n=1. Checking this number with the third pair leads to a contradiction. i+1 can never be i and it cannot be i+n+1 either (not for any n>0 and then obviously not for n=1). So the non-repetition rule holds also when a down diagonal enters an up turn.
Now we have the case when a down diagonal exits an up turn. We have.
i, j
i-1, j (straight up)
i-2, j-1 (diagonally up)
Insertion of j=i+n gives
i, i+n
i-1, i+n
i-2, i+n-1
Here we identify i+n as the only number present in both of the first two pairs. Can it be found in the third pair? No because i+n cannot be i-2 nor can it be i+n-1 for any n>0. And the non-repetition rule holds also in this case.
The remaning three cases; An up diagonal, an up diagonal entering a down turn, and an up diagonal exiting a down turn all give the same result. The non-repetition rule holds.
Conclussion: The algorithm generates a pair sequence which obeys the non-repetition rule indeed. (but I strongly recommend you to check the proof before relying on it)
Hi
there is a shorter proof:
Select two out of N is (N) over (2) --> N*(N-1)/(1*2) :-)
Bluescreen: Look here
http://en.wikipedia.org/wiki/Combina...k-combinations
Best regards,
Marco
Possibly, but this isn't about the number of pairs, nor is it about generating all pairs. It's about ordering the pairs in sequence obeying a certain non-repetition rule.Quote:
Originally Posted by GMarco
Oh sorry, i did not read carefully.
So my proof would be:
1. as long as you move in the diagonal both (i) and (j) are changing.
2. If you step from one diagonal to another sometimes i or j will stay the same
So follow the diagonals as long as possible, then switch.
GMarco
That's not a proof, that's an algorithm similar to the one I suggested in my first post. Then I proved its correctness in a follow-up post.Quote:
Originally Posted by GMarco
Hi,
your "proof" does not work for N=2. If you check only all subsequences of the length 3, you do not check anything if there is no subsequence of the length 3. So your proof does tell us nothing about the case N=2. Your proof is incomplete, and therefore it is wrong.
Maybe you will tell that this case N=2 is trivial (it is), but you forgot to mention it. :-)
We both gave wrong proofs.
I additionally did not read carefully in the first place. Therefore I am sorry.
Peace?
GMarco
The proof is informal. I posted it for peer review and your objection is thankfully noted. But at this stage I'm mostly interested in whether it holds in principle. If not and no other proof can be found I must withdraw the algorithm I suggested to the OP.Quote:
Originally Posted by GMarco