
August 4th, 2011, 04:29 AM
#1
List combination algorithm
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:
12
23
34
14
13
42
Can you help me? Thanks in advance!
Regards
Bluescreen

August 4th, 2011, 05:09 PM
#2
Re: List combination algorithm
You can represent the pairs in a table like this.
Code:
1 2 3 4
1 x x x
2 x x
3 x
4
For example the upper left x represents the 1,2 pair.
Now the problems is to visit the x in a sequence that obeys the nonrepetition rule. For example you did it like this,
Code:
1 2 3 4
1 1 5 4
2 2 6
3 3
4
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 5
1 1 7 8 10
2 2 6 9
3 3 5
4 4
5
And this is the corresponding list,
1,2
2,3
3,4
4,5
3,5
2,4
1,3
1.4
2,5
1,5
Last edited by nuzzle; August 5th, 2011 at 08:16 AM.

August 7th, 2011, 04:31 AM
#3
Re: List combination algorithm
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.
Code:
1 2 3 4 5
1 1 7 8 10
2 2 6 9
3 3 5
4 4
5
It's given that j>i. This can be restated as j=i+n where n>0.
The idea behind the proof is to check every possible subsequence consisting of three successive pairs and make sure that it obeys the nonrepetition rule. This rule states that if a number is present in both the two first pairs of a 3sequence it must not be present in the third pair. If this holds for any 3sequence it holds for the full sequence as a whole.
There are six distinctly different 3sequence 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 nonrepetition rule holds in every down diagonal 3sequence.
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 nonrepetition 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
i1, j (straight up)
i2, j1 (diagonally up)
Insertion of j=i+n gives
i, i+n
i1, i+n
i2, i+n1
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 i2 nor can it be i+n1 for any n>0. And the nonrepetition 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 nonrepetition rule holds.
Conclussion: The algorithm generates a pair sequence which obeys the nonrepetition rule indeed. (but I strongly recommend you to check the proof before relying on it)
Last edited by nuzzle; August 7th, 2011 at 05:54 AM.

August 7th, 2011, 06:10 AM
#4
Re: List combination algorithm
Hi
there is a shorter proof:
Select two out of N is (N) over (2) > N*(N1)/(1*2) :)
Bluescreen: Look here
http://en.wikipedia.org/wiki/Combina...kcombinations
Best regards,
Marco

August 7th, 2011, 06:57 AM
#5
Re: List combination algorithm
Originally Posted by GMarco
there is a shorter proof:
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 nonrepetition rule.

August 7th, 2011, 07:06 AM
#6
Re: List combination algorithm
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

August 7th, 2011, 07:44 AM
#7
Re: List combination algorithm
Originally Posted by GMarco
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.
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 followup post.

August 7th, 2011, 01:16 PM
#8
Re: List combination algorithm
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

August 7th, 2011, 02:52 PM
#9
Re: List combination algorithm
Originally Posted by GMarco
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. :)
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.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
