## Combinations algorithm and property

**Moderators:** gmalivuk, Moderators General, Prelates

### 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.

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.

### Re: Combinations algorithm and property

Goahead52 wrote:1-2-3-4-5

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?

### 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.

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.

### Re: Combinations algorithm and property

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

### Re: Combinations algorithm and property

measure wrote:Goahead52 wrote:1-2-3-4-5

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

### 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.

### 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.

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.

### 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.

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.

### 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.

### Re: Combinations algorithm and property

Goahead52 wrote: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=10`

k=5

gray=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:**

### 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.

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.

### 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:

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)

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)

### 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.

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.

### 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

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

Now add a second one

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

Though

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:**

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

Now add a second one

**Spoiler:**

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

Though

### 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:**

Here is the output for n=7, k=3:

**Spoiler:**

### 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 sys

def 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 p

def 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

^{n}C

_{r}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

`123`

137

136

135

134

147

146

145

157

156

167

567

457

456

467

347

346

345

357

356

367

237

236

235

234

247

246

245

257

256

267

127

126

125

124

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

Code: Select all

`12345`

12357

12356

12367

13567

13457

13456

13467

14567

34567

23567

23457

23456

23467

24567

12567

12457

12456

12467

12347

12346

### Re: Combinations algorithm and property

@PeteP

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

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

### 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

`...`

134

147

...

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

### 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

`...`

134

147

...

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.

### 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.

Converting this to a general algorithm is left as an exercise for the reader

Code: Select all

`111000`

110100

110010

110001

101001

100101

100011

100110

101010

101100

011100

011010

011001

010101

010011

010110

001110

001101

001011

000111

There's no such thing as a funny sig.

### Who is online

Users browsing this forum: No registered users and 16 guests