## Combinations algorithm and property

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Combinations algorithm and property

Hi everyone,

Is there an algorithm generating combinations C(n,k) such as the ouput order has this property :
each k-uplet shares exactly (k-1) elements with its 2 neighbours.

Example :

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

the combination 1-2-3-4-6 shares 4 numbers (1-2-3-4) with the previous 1-2-3-4-5 and 4 numbers (1-2-3-6) with the next 1-2-3-6-7

No need to store the combinations and sort them after is required.
They are sorted as they are generated.
If such algorithm exists can we produce others such as some property is achieved by the generator algorithm.

Thank you for any clue.

measure
Posts: 126
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

### Re: Combinations algorithm and property

1-2-3-4-6
1-2-3-6-7

Does the algorithm have to produce all the possible combinations in sorted (assuming numeric low-high) order? If so, shouldn't 1-2-3-5-6 or 1-2-3-4-7 be the third result? Otherwise, how many k-uplets are required?

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Combinations algorithm and property

Sorry I forget to add that the n-th combination has 2 neighbours : the first combination and the (n-1)-th combination.
It is like if all the combinations are placed as points in the perimeter of a circle.
The property is fulfilled for all the combinations then.

PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

### Re: Combinations algorithm and property

I assume no double elements in the tuples? (Like 1-2-3-4-4 with two fours.)

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Combinations algorithm and property

measure wrote:
1-2-3-4-6
1-2-3-6-7

Does the algorithm have to produce all the possible combinations in sorted (assuming numeric low-high) order? If so, shouldn't 1-2-3-5-6 or 1-2-3-4-7 be the third result? Otherwise, how many k-uplets are required?

By generating the combinations as they are (output order) the property is respected.
The algorithm is supposed to all the combinations (k-uplets) each one ONCE.
For some value of n and k any algorithm will fulfill the property :
Example n=6 k=5

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Combinations algorithm and property

PeteP wrote:I assume no double elements in the tuples? (Like 1-2-3-4-4 with two fours.)

Yes.

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Combinations algorithm and property

In other words -
A set with n elements has nCk subsets of k elements.
Find a way to put these subsets in a (circular) list such that each adjacent pair of subsets in the list have k-1 elements in common.
Preferably find an algorithm that allows you to generate such a list.

This feels a bit like a Gray Code, but I suspect that there is not such an easy algorithm.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Combinations algorithm and property

There are 6 5-uplets on 6 numbers :

1-2-3-4-5
1-2-3-4-6
1-2-3-5-6
1-2-4-5-6
1-3-4-5-6
2-3-4-5-6

You could place them in any order each combination will share 4 elements with its neighbours.

For (10,5) it is not the case. You have to sort them in many ways such as each combination share 4 numbers with its 2 neighbours.
How many ways is itself a hard problem of enumeration?
But that is another problem.
Last edited by Goahead52 on Tue Jun 02, 2015 3:27 pm UTC, edited 2 times in total.

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Combinations algorithm and property

jaap wrote:In other words -
A set with n elements has nCk subsets of k elements.
Find a way to put these subsets in a (circular) list such that each adjacent pair of subsets in the list have k-1 elements in common.
Preferably find an algorithm that allows you to generate such a list.

This feels a bit like a Gray Code, but I suspect that there is not such an easy algorithm.

Similar but it does not answer to the question except if you use some shortcut.

Nicias
Posts: 164
Joined: Tue Aug 13, 2013 4:22 pm UTC

### Re: Combinations algorithm and property

jaap wrote:In other words -
A set with n elements has nCk subsets of k elements.
Find a way to put these subsets in a (circular) list such that each adjacent pair of subsets in the list have k-1 elements in common.
Preferably find an algorithm that allows you to generate such a list.

This feels a bit like a Gray Code, but I suspect that there is not such an easy algorithm.

Similar but it does not answer to the question except if you use some shortcut.

I'm not sure about a shortcut, but it this seems to work for a few random n,k pairs. Take the Gray code on n binary digits. Use only the entries with k one's. Then read off the positions of these 1's. For instance. N=5, k=3:
Gray code:

Code: Select all

`0000, 00001, 00011, 00010, 00110, 00111, 00101, 00100, 01100, 01101, 011110, 01110, 01010, 01011, 01001, 01000, 11000, 11001, 11011, 11010, 11110, 11111, 11101, 11100, 10100, 10101, 10111, 10110, 10010, 10011, 10001, 10000`

Only entries with 3 1's:

Code: Select all

`00111,  01101,  01110,  01011,  11001,  11010, 11100,  10101,  10110,  10011`

Translate to positions of 1's:

Code: Select all

`345, 235, 234, 245, 125, 124, 123, 135, 134, 145`

Mathematica code to do this:

Code: Select all

`n=10k=5gray=Nest[Join[#,Length[#]+Reverse[#]]&,{0},n];BaseForm[%,2];gray2=Select[gray,DigitCount[#,2,1]==k&];BaseForm[%,2];gray2cyc=Join[gray2[[2;;]],{gray2[[1]]}];Union[DigitCount[BitXor[gray2,gray2cyc],2,1]]graydigits = Join[Table[0,{i,1,n-Length[#]}],#] & /@ IntegerDigits[gray2,2];Flatten[Position[#,1]] &/@ graydigits`

The "check" line should just return "{2}" if this meets your needs.
For example, output with n=10 and k=5
Spoiler:

Code: Select all

`105{2}{{6,7,8,9,10},{5,6,8,9,10},{5,6,7,8,10},{5,6,7,8,9},{5,6,7,9,10},{5,7,8,9,10},{4,5,8,9,10},{4,5,7,8,10},{4,5,7,8,9},{4,5,7,9,10},{4,5,6,7,10},{4,5,6,7,9},{4,5,6,7,8},{4,5,6,8,10},{4,5,6,8,9},{4,5,6,9,10},{4,6,8,9,10},{4,6,7,8,10},{4,6,7,8,9},{4,6,7,9,10},{4,7,8,9,10},{3,4,8,9,10},{3,4,7,8,10},{3,4,7,8,9},{3,4,7,9,10},{3,4,6,7,10},{3,4,6,7,9},{3,4,6,7,8},{3,4,6,8,10},{3,4,6,8,9},{3,4,6,9,10},{3,4,5,6,10},{3,4,5,6,9},{3,4,5,6,8},{3,4,5,6,7},{3,4,5,7,10},{3,4,5,7,9},{3,4,5,7,8},{3,4,5,8,10},{3,4,5,8,9},{3,4,5,9,10},{3,5,8,9,10},{3,5,7,8,10},{3,5,7,8,9},{3,5,7,9,10},{3,5,6,7,10},{3,5,6,7,9},{3,5,6,7,8},{3,5,6,8,10},{3,5,6,8,9},{3,5,6,9,10},{3,6,8,9,10},{3,6,7,8,10},{3,6,7,8,9},{3,6,7,9,10},{3,7,8,9,10},{2,3,8,9,10},{2,3,7,8,10},{2,3,7,8,9},{2,3,7,9,10},{2,3,6,7,10},{2,3,6,7,9},{2,3,6,7,8},{2,3,6,8,10},{2,3,6,8,9},{2,3,6,9,10},{2,3,5,6,10},{2,3,5,6,9},{2,3,5,6,8},{2,3,5,6,7},{2,3,5,7,10},{2,3,5,7,9},{2,3,5,7,8},{2,3,5,8,10},{2,3,5,8,9},{2,3,5,9,10},{2,3,4,5,10},{2,3,4,5,9},{2,3,4,5,8},{2,3,4,5,7},{2,3,4,5,6},{2,3,4,6,10},{2,3,4,6,9},{2,3,4,6,8},{2,3,4,6,7},{2,3,4,7,10},{2,3,4,7,9},{2,3,4,7,8},{2,3,4,8,10},{2,3,4,8,9},{2,3,4,9,10},{2,4,8,9,10},{2,4,7,8,10},{2,4,7,8,9},{2,4,7,9,10},{2,4,6,7,10},{2,4,6,7,9},{2,4,6,7,8},{2,4,6,8,10},{2,4,6,8,9},{2,4,6,9,10},{2,4,5,6,10},{2,4,5,6,9},{2,4,5,6,8},{2,4,5,6,7},{2,4,5,7,10},{2,4,5,7,9},{2,4,5,7,8},{2,4,5,8,10},{2,4,5,8,9},{2,4,5,9,10},{2,5,8,9,10},{2,5,7,8,10},{2,5,7,8,9},{2,5,7,9,10},{2,5,6,7,10},{2,5,6,7,9},{2,5,6,7,8},{2,5,6,8,10},{2,5,6,8,9},{2,5,6,9,10},{2,6,8,9,10},{2,6,7,8,10},{2,6,7,8,9},{2,6,7,9,10},{2,7,8,9,10},{1,2,8,9,10},{1,2,7,8,10},{1,2,7,8,9},{1,2,7,9,10},{1,2,6,7,10},{1,2,6,7,9},{1,2,6,7,8},{1,2,6,8,10},{1,2,6,8,9},{1,2,6,9,10},{1,2,5,6,10},{1,2,5,6,9},{1,2,5,6,8},{1,2,5,6,7},{1,2,5,7,10},{1,2,5,7,9},{1,2,5,7,8},{1,2,5,8,10},{1,2,5,8,9},{1,2,5,9,10},{1,2,4,5,10},{1,2,4,5,9},{1,2,4,5,8},{1,2,4,5,7},{1,2,4,5,6},{1,2,4,6,10},{1,2,4,6,9},{1,2,4,6,8},{1,2,4,6,7},{1,2,4,7,10},{1,2,4,7,9},{1,2,4,7,8},{1,2,4,8,10},{1,2,4,8,9},{1,2,4,9,10},{1,2,3,4,10},{1,2,3,4,9},{1,2,3,4,8},{1,2,3,4,7},{1,2,3,4,6},{1,2,3,4,5},{1,2,3,5,10},{1,2,3,5,9},{1,2,3,5,8},{1,2,3,5,7},{1,2,3,5,6},{1,2,3,6,10},{1,2,3,6,9},{1,2,3,6,8},{1,2,3,6,7},{1,2,3,7,10},{1,2,3,7,9},{1,2,3,7,8},{1,2,3,8,10},{1,2,3,8,9},{1,2,3,9,10},{1,3,8,9,10},{1,3,7,8,10},{1,3,7,8,9},{1,3,7,9,10},{1,3,6,7,10},{1,3,6,7,9},{1,3,6,7,8},{1,3,6,8,10},{1,3,6,8,9},{1,3,6,9,10},{1,3,5,6,10},{1,3,5,6,9},{1,3,5,6,8},{1,3,5,6,7},{1,3,5,7,10},{1,3,5,7,9},{1,3,5,7,8},{1,3,5,8,10},{1,3,5,8,9},{1,3,5,9,10},{1,3,4,5,10},{1,3,4,5,9},{1,3,4,5,8},{1,3,4,5,7},{1,3,4,5,6},{1,3,4,6,10},{1,3,4,6,9},{1,3,4,6,8},{1,3,4,6,7},{1,3,4,7,10},{1,3,4,7,9},{1,3,4,7,8},{1,3,4,8,10},{1,3,4,8,9},{1,3,4,9,10},{1,4,8,9,10},{1,4,7,8,10},{1,4,7,8,9},{1,4,7,9,10},{1,4,6,7,10},{1,4,6,7,9},{1,4,6,7,8},{1,4,6,8,10},{1,4,6,8,9},{1,4,6,9,10},{1,4,5,6,10},{1,4,5,6,9},{1,4,5,6,8},{1,4,5,6,7},{1,4,5,7,10},{1,4,5,7,9},{1,4,5,7,8},{1,4,5,8,10},{1,4,5,8,9},{1,4,5,9,10},{1,5,8,9,10},{1,5,7,8,10},{1,5,7,8,9},{1,5,7,9,10},{1,5,6,7,10},{1,5,6,7,9},{1,5,6,7,8},{1,5,6,8,10},{1,5,6,8,9},{1,5,6,9,10},{1,6,8,9,10},{1,6,7,8,10},{1,6,7,8,9},{1,6,7,9,10},{1,7,8,9,10}}`

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Combinations algorithm and property

Thank you.
But there is a problem in your algorithm.
First you generate all the 2^5 then you select the 3 1`ones and in final you use your code.
There is a storage step which is not required.
Imagine n=1000 how are going to select the 5-uples without storage?
Is is not a shortcut then.
Such algorithm giving directly a sequence of combinations sorted such as the property above is fulfilled is possible.
Not only sharing (k-1) elements but even (k-i) elements with i varying from 1 to k.

Nicias
Posts: 164
Joined: Tue Aug 13, 2013 4:22 pm UTC

### Re: Combinations algorithm and property

Yes it is.
You can translate from "125" to 11001, then you can translate from 11001 to 17. Then you incriment and convert and check until you get 3 1's. Then you convert back. Something like this:

Code: Select all

`comb nextComb(comb current, int n){   int count;   int k;   gray currentGray;   int max;   max = 1 << n   currentGray = comb2gray(current);   k= count1s(currentGray);   count = gray2int(currentGray)+1;   while ( count1s(int2gray(count)) != k ) count=(count+1) % max ;   return(gray2comb(int2gray(count));}`

Hopefully you can see how to make the functions comb2gray gray2comb from my example. You can make the int2gray and gray2int from
http://en.wikipedia.org/wiki/Gray_code# ... _Gray_code
I've been a little lazy about my types.

for example 125 -> 11001 (notice 3 1's) -> 17

18-> 11011 (nope)
19-> 11010 (yup)
11010 -> 124 (next combination)

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Combinations algorithm and property

Anyway your algorithm does NOT generate directly the sorted list.
That is not what I`m asking for.
It is solution for sure I told you that before (gray with some sort of shortcut).
But it is NOT the solution expected.
Let me put it my way.
For each property required you generate an order some sort of natural order (1,2,3,4..............n). Each value of this order could be converted into combination.
For each n-th you convert it simultaneously as combination.
So the output order generated fulfill exactly the property required.
No storage no loop no if no while.

Thank you very much for your interest.

PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

### Re: Combinations algorithm and property

Out of curiosity does this have an purpose?

The loop part (that the last one is the neighbour of the first one) makes this tricky.

Without that part I would solve it by methodically moving freespaces (assuming I didn't misunderstand something).
If you begin with
1-2-3-4-5
I would start by moving a freespace (see below what I mean) up (or down) through the numbers
Spoiler:

Code: Select all

`2)_ 2 3 4 5 63)1 _34564)12_4565)123_566)1234_6 `

As you see only one number gets replaced at a time and for the first round the freespace is at place n-1.
Spoiler:

Code: Select all

`7)_2345_7 8)1_345_7 9)12_45_7 10)123_5_7 11)1234__7 If you just add new gaps like this their position is predictable and can be calculated from the number. But you only get 20 of the combinations I thinkTo get all 126 possible combinations you need to move both spaces one down now and then move the other one down step by step and so on.12)123__67 12)12_4_67 That makes it harder to calculate the positions from the number but I think it's still possible`

However this forms no circle, but I wonder whether you could do something similiar.
Though

jaap
Posts: 2091
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Combinations algorithm and property

PeteP wrote:The loop part (that the last one is the neighbour of the first one) makes this tricky.

Without that part I would solve it by methodically moving freespaces (assuming I didn't misunderstand something).

That does indeed work as far as I can tell for a non-circular list. Here is some Java code that does exactly this. It is not the most elegant code, but it's the best I could do in a short time.
Spoiler:

Code: Select all

`public class Comb {   public static void main(String[] args) {      int n=7;      int k=3;      long numcomb = comb(n,k);            // print list of subsets      for( int i=0; i<numcomb; i++ ){         System.out.println(idx2Comb(i,n,k));      }   }   // Converts an index in [0,nCk) into string representation of subset   public static String idx2Comb(int idx, int n, int k){      String pre="";      String post="";      int low = 1;      int high = n;      boolean reverse = false;      boolean reverseNext = false;            while(low<=high && k>0){         int blocklength = comb(high-low,k-1);         if(idx<blocklength){            if( reverse ) {               post=high+post;               high--;            }else{               pre = pre+low;               low++;            }            k--;            reverse = reverseNext;         }else{            idx-=blocklength;            if( reverse ) high--;            else low++;            reverseNext = !reverseNext;         }      }      return pre+post;   }      // returns nCk = n!/ k!(n-k)!   public static int comb(int n, int k){      k = Math.min(k,n-k);      int c = 1;      for( int i=1; i<=k; i++ ){         c = c*(n+1-i)/i;      }      return c;   }}`
It directly converts the index number of the list to the subset that should be in that position on the list. Unfortunately the subset at the top of the list (which will contain the k smallest elements) and the subset at the bottom of the list (which will contain the k largest elements) are not adjacent.
Here is the output for n=7, k=3:
Spoiler:

Code: Select all

`123124125126127137136135134145146147157156167267257247237236246256245235234345346347357356367467457456567`

PM 2Ring
Posts: 3668
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Mid north coast, NSW, Australia

### Re: Combinations algorithm and property

Goahead52 wrote:Is there an algorithm generating combinations C(n,k) such as the ouput order has this property :
each k-uplet shares exactly (k-1) elements with its 2 neighbours.

Yes, there is.

It's Algorithm 452: enumerating combinations of m out of n objects by C. N. Liu and D. T. Tang.

Here's an implementation I wrote in Python 2 a few years ago.

Code: Select all

`#! /usr/bin/env python''' Generate combinations of length k from a set of n items    Algorithm #452 by Liu & Tang, Communications of the ACM 16, p. 485 (1973).    This implementation is derived from Programming Classics by Ian Oliver, p.101.    Note: Oliver uses 1-based indexing :(     Converted to use 0-based indexing :)    "Pythonized" & converted to a generator    Written by PM 2Ring 2010.11.21'''import sysdef ch(n, r):    ''' Binomial coefficient, nCr, aka the "choose" function        n! / (r! * (n - r)!)    '''    p = 1    for i in xrange(1, min(r, n - r) + 1):        p *= n        p //= i        n -= 1    return pdef combo(n, k):    ''' Unordered combination generator.         Yields combinations in bitstring form.    '''    #Create the initial bitstring    a = k*[1] + (n - k)*[0]    yield a    for i in xrange(ch(n, k) - 1):        #Find where rightmost bitchange occurs        lastbit = a[-1]        change = n - 2        while change and a[change] == lastbit:            change -= 1        #Find the position of the next one bit at or preceding the bitchange        nextone = change        while nextone and not a[nextone]:            nextone -= 1        #Determine position of rightmost zero        rightzero = change if lastbit else n - 1        #Determine which bits to exchange         if (rightzero + k - n) % 2:            b1, b2 = change, min(change + lastbit + 1, n - 1)        else:            if nextone:                b1 = nextone - 1                b2 = rightzero if a[b1] else change + lastbit            else:                b1, b2 = 0, rightzero         #Do the bit exchange        a[b1], a[b2] = a[b2], a[b1]          yield a def main():    #get args    if len(sys.argv) < 3:        print 'Generate all combinations of the elements of a string\n' +\        'Usage: %s string substring_length' % sys.argv[0]        exit(1)    s = sys.argv[1]    k = int(sys.argv[2])    n = len(s)    r = xrange(n)    for a in combo(n, k):        #print a        print ''.join([s[j] for j in r if a[j]])if __name__ == '__main__':    main() `

This code computes nCr so that it knows when to stop. Otherwise it would cycle indefinitely through the combinations. Alternatively, we could use a while loop that stops when the bitstring a returns to its initial value, either by direct comparison, or by checking the position of the rightmost 1 or leftmost 0 in the bitstring, but all those methods are less efficient than using a simple counter.

Here's the script's output for string '1234567' with a substring_length of 3, i.e., the same set of combinations as jaap's code.

Code: Select all

`123137136135134147146145157156167567457456467347346345357356367237236235234247246245257256267127126125124`

And now the output for string '1234567' with a substring_length of 4.

Code: Select all

`123451235712356123671356713457134561346714567345672356723457234562346724567125671245712456124671234712346`

Posts: 431
Joined: Thu Oct 16, 2014 9:28 am UTC

### Re: Combinations algorithm and property

@PeteP

The purpose is for a cardgame but there are other uses (mazes or cryptography for example)

drachefly
Posts: 195
Joined: Thu Apr 23, 2009 3:25 pm UTC

### Re: Combinations algorithm and property

PM 2Ring wrote:
Goahead52 wrote:Is there an algorithm generating combinations C(n,k) such as the ouput order has this property :
each k-uplet shares exactly (k-1) elements with its 2 neighbours.

Yes, there is.
...
Here's the script's output for string '1234567' with a substring_length of 3, i.e., the same set of combinations as jaap's code.

Code: Select all

`...134147...`

Maybe I missed something, but this doesn't seem to fit.

Thesh
Posts: 6402
Joined: Tue Jan 12, 2010 1:55 am UTC

### Re: Combinations algorithm and property

drachefly wrote:
PM 2Ring wrote:
Goahead52 wrote:Is there an algorithm generating combinations C(n,k) such as the ouput order has this property :
each k-uplet shares exactly (k-1) elements with its 2 neighbours.

Yes, there is.
...
Here's the script's output for string '1234567' with a substring_length of 3, i.e., the same set of combinations as jaap's code.

Code: Select all

`...134147...`

Maybe I missed something, but this doesn't seem to fit.

How so? They share exactly two elements (1,4) which is in line with the requirement.
Summum ius, summa iniuria.

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

### Re: Combinations algorithm and property

This seems more like a problem in ASCII art than anything else. Anyone remember "scrollees"? Back when plaintext was ubiquitous? Evidently Google doesn't, so probably I'm spelling it wrong. But yeah, it's not that hard. Here's one for comb(6,3). To convert it to subsets just take each bit position to represent an item of the set of n items, and for each subset include a given item if its bit is 1.

Code: Select all

`111000110100110010110001101001100101100011100110101010101100011100011010011001010101010011010110001110001101001011000111`
Converting this to a general algorithm is left as an exercise for the reader
There's no such thing as a funny sig.