A Permutation Algorithm Challenge

[CraigD]

I stumbled across this kinda nifty choice permuting algorithm yesterday:

1. Place the N members to be permuted into 2 rows of equal length (number of positions), and a 1 “odd-man-out” position to the left of the leftmost position of the top row. N must be odd.
   
2. Chose pairs of members opposite one another in opposite rows.
   
3. Rotate the arrangement 1 position, leftmost member of the top row to the OMOP, OMOP member to the leftmost position of the bottom row, rightmost bottom to rightmost top, etc.
   
4. Repeat steps 2 through 3 N (counting the first) times
   

Example, for N=5:

1,2,3  2:5 3:4
 5,4
2,3,4  3:1 4:5
 1,5
3,4,5  4:2 5:1
 2,1
4,5,1  5:3 1:2
 3,2
5,1,2  1:4 2:3
 4,3

 

I see no computational advantage for this algorithm over other common “choose 2 of n, order not important” ones (unless possibly you’re implementing it in people standing in a field, for which it is well suited :)).

 

My challenge is this: extend (generalize) this algorithm to work for the “chose 3 of n” or higher. Or, if this is impossible, prove it.

[phillip1882]

so basically you want to group people together such that everyone is grouped with every other member at least once, and no group is repeated.

this looks like the social golfer problem. for the more strict case of no one being grouped with the same person more than once, it is generally unsolveable.

with this less restricted case however, not really sure.

[sanctus]

It seems to me that it is enough that for m out of N one has that N>2*m. Then you can apply exactly the same algorithm.

 

Example 3 out of 5 it does not work, but 3 out of 7 gives

1 2 3 4   2:7, 3:6, 4:5
 7 6 5

2 3 4 5   3:1, 4:7, 5:6
 1 7 6

3 4 5 6   4:2, 5:1, 6:7
 2 1 7

4 5 6 7   5:3, 6:2, 7:1
 3 2 1

5 6 7 1   6:4, 7:3, 1:2
 4 3 2

6 7 1 2   7:5, 1:4, 2:3
 5 4 3

7 1 2 3   1:6, 2:5, 3:4
 6 5 4

 

But how to prove it that given N>2*m the algorithm I have no good idea atm....

[phillip1882]

i might have the wrong idea, but the way i read it, when chosing 3 out of the 5 you want groups of 3 not 2,

so...

1 2 3   1:2:3
 5 4

2 3 4  2:3:4
 1 5 
etc.
with 7...

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

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

however, as you can see, 7 will never be grouped with 3, so the algorithm doesn't work here.

[sanctus]

Actually i am pretty sure that m out of N=2*m+1 always works. But I see it already breaking down if one has N'>N...take for example 3 out of 9 then it does not seem to work

[sanctus]

Ok, waiting for a simulation to finish so I invested a bit time in this. I think I can prove that for m out of N=2m+1 it owrks.

 

In terms of m and N, the first row always has N-m elements and the second one has N-m-1.

 

For m=2 and m=3 we already checke it. So if we suppose it works for m=n and check if then it works for m=n+1 too:

The 2 rows can be written

 1     2     3  ...  2m+1-m-1   2m+1-m
   2m+1-m+1 ...          m*2     m*2+1

 

Developping:

 

 1      2      3  ...   n+1    n+2
       n+3    n+4 ...  2n+2    2n+3

 

And now I got stuck ;-) Because I expected that if take away the last pair (i.e. (n+2):(2n+3)) we would have what we we had at m=n; while we have this only in the first row, while in the second it is different :-(. Any ideas how to get around this?

[sanctus]

i might have the wrong idea, but the way i read it, when chosing 3 out of the 5 you want groups of 3 not 2,

so...

1 2 3   1:2:3
 5 4

2 3 4  2:3:4
 1 5 
etc.
with 7...

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

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

however, as you can see, 7 will never be grouped with 3, so the algorithm doesn't work here.

I noted that, that is why I tried to prove that it works only for n out of 2m+1. Or maybe I get you worng...

[sanctus]

Ok got what you mean:I found a way to find m pairs out of 2m+1 elements which is not what the general algorithm proposed by the OP was supposed to do. Well end of a long day for me, with the normal effects ;-)

[CraigD]

My challenge is this: extend (generalize) this algorithm to work for the “chose 3 of n” or higher. Or, if this is impossible, prove it.

I’d better clarify my challenge!

 

In the OP, I demonstrated an algorithm that gives all choices of C=2 of N (where N is odd) via a single rotation of the list of members to chose from.

 

What I’m asking for is an algorithm that give all choices of C>2 of N (where N may be restricted in any way you like) via a single rotation of the list, or a proof that such an algorithm is impossible.

 

Put generally, such an algorithm can be described by a collection of C-tuples of positions in the list (ordinals). In the OP demonstration case of the C=2,N=5, this collection is ((2,5),(3,4)). In general, any C=2 algorithm like the one described has 2-tuple (pair) collection [imath]\left((2,N),(3,N-1) ... \left(\frac{N-1}{2}, \frac{N-1}{2}+1 \right)\right)[/imath]

 

The ordinals in the OP algorithms are constants. You can assume this to be a condition of the challenge, or allow them to be any expression.

 

Here are a couple of examples of Ns and 3-tuple collections that don’t work:

• From Phillip’s post #2: N=7, ((2,3,4),(7,6,5))
  
• A new one of mine: N=8, ((2,7,5),(3,8,4)), which corresponds to a “people in a field” arrangement like this:

  1  2 3
    7 8
  6  5 4

  
  

 

It’s pretty simple to show why these don’t work, by comparing the number of choices given by the formula N!/((N-C)! C!). Any solution will generate Nm choices, where m is the algorithm’s number of C-tuples. I’ll stop here, ‘cause I think I’m about to give something away. :)

[phillip1882]

so yeah: i dont see any possible way to extend that algorthim generally.

basically no matter how you arrange the rows and columns,

n C r is greater than n*n/r.

 

you would need some intermedate steps from the standard rotation to make it work.