Combinations algorithm and property

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Combinations algorithm and property

Postby Goahead52 » Tue Jun 02, 2015 2:02 pm UTC

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.

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

Re: Combinations algorithm and property

Postby measure » Tue Jun 02, 2015 2:55 pm UTC

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?

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

Re: Combinations algorithm and property

Postby Goahead52 » Tue Jun 02, 2015 2:57 pm UTC

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.

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

Re: Combinations algorithm and property

Postby PeteP » Tue Jun 02, 2015 3:00 pm UTC

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

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

Re: Combinations algorithm and property

Postby Goahead52 » Tue Jun 02, 2015 3:01 pm UTC

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

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

Re: Combinations algorithm and property

Postby Goahead52 » Tue Jun 02, 2015 3:01 pm UTC

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

Yes.

User avatar
jaap
Posts: 2087
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Combinations algorithm and property

Postby jaap » Tue Jun 02, 2015 3:19 pm UTC

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.

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

Re: Combinations algorithm and property

Postby Goahead52 » Tue Jun 02, 2015 3:22 pm UTC

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.

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

Re: Combinations algorithm and property

Postby Goahead52 » Tue Jun 02, 2015 3:23 pm UTC

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: 162
Joined: Tue Aug 13, 2013 4:22 pm UTC

Re: Combinations algorithm and property

Postby Nicias » Tue Jun 02, 2015 4:10 pm UTC

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:

Code: Select all

10

5

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

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

Re: Combinations algorithm and property

Postby Goahead52 » Tue Jun 02, 2015 5:05 pm UTC

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: 162
Joined: Tue Aug 13, 2013 4:22 pm UTC

Re: Combinations algorithm and property

Postby Nicias » Tue Jun 02, 2015 5:53 pm UTC

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)

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

Re: Combinations algorithm and property

Postby Goahead52 » Tue Jun 02, 2015 6:54 pm UTC

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.

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

Re: Combinations algorithm and property

Postby PeteP » Tue Jun 02, 2015 7:32 pm UTC

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 6
3)1 _3456
4)12_456
5)123_56
6)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.
Now add a second one
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 think
To 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

User avatar
jaap
Posts: 2087
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Combinations algorithm and property

Postby jaap » Tue Jun 02, 2015 10:41 pm UTC

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

123
124
125
126
127
137
136
135
134
145
146
147
157
156
167
267
257
247
237
236
246
256
245
235
234
345
346
347
357
356
367
467
457
456
567

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

Re: Combinations algorithm and property

Postby PM 2Ring » Wed Jun 03, 2015 7:59 am UTC

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] + (- 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

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

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

Re: Combinations algorithm and property

Postby Goahead52 » Wed Jun 03, 2015 12:58 pm UTC

@PeteP

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

User avatar
drachefly
Posts: 194
Joined: Thu Apr 23, 2009 3:25 pm UTC

Re: Combinations algorithm and property

Postby drachefly » Wed Jun 03, 2015 8:20 pm UTC

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.

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6328
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Combinations algorithm and property

Postby Thesh » Wed Jun 03, 2015 8:49 pm UTC

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.

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

Re: Combinations algorithm and property

Postby Wildcard » Thu Jun 04, 2015 4:36 am UTC

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

111000
110100
110010
110001
101001
100101
100011
100110
101010
101100
011100
011010
011001
010101
010011
010110
001110
001101
001011
000111
Converting this to a general algorithm is left as an exercise for the reader :wink:
There's no such thing as a funny sig.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 23 guests