Request for Combination algo in C/C++

3 views
Skip to first unread message

Lee Yen Hoe

unread,
Oct 27, 1996, 2:00:00 AM10/27/96
to


Hi,

A small part in a program that I am coding now requires this :

Given an array of integer of size N, generate all combination.

For example :

An array of size 4, with 1,2,3,4. I wanted to generate :

1
2
3
4
1,2
1,3
1,4
2,3
2,4
3,4
1,2,3
1,2,4
1,3,4
2,3,4
1,2,3,4

Note that I don't need 3,1 for instance, because it's the same as 1,3.

Would be grateful if anyone could provide some pointer (or code fragment if yo
have). All other parts of my program works, except this is giving me some
problem.

Regards
Yen Hoe

Jens Andreasen

unread,
Oct 28, 1996, 3:00:00 AM10/28/96
to

/* Print all combinations in a set of size n, recursive variant.
*/

#include <stdio.h>
#define N 4

char a[N];

void pr(int n){do if(a[n])printf(" %d",N-n);while(n--); puts("");}

set(int n){

if(n==N)return 1;

a[n]=0;
if(set(n+1))pr(n);
a[n]=1;
if(set(n+1))pr(n);
return 0;
}

main(void){ set(0); return 0;}

/* ------------------------------------------------------------- */


// Jens M Andreasen

"Stay ahead of the competition, do their homework!"

Bob Calbridge

unread,
Oct 28, 1996, 3:00:00 AM10/28/96
to

>Hi,

>For example :

>Regards
>Yen Hoe

Not exactly what I'd call combinations in the mathematical sense and
not a permutation either. You leave a question or so hanging too.
Is 4 a fixed quantity or is the quantity variable? Do you just want
to print them out or do something else with the combination? That is,
do you need the returned values applied to another process? Does the
order in which they're generated matter?

I don't have time to work through it but if order didn't matter I
could see a bit of recursion working to arrive at the variable number
of combinations with a simple loop inside. The recursed function
would have to be passed the current value of the calling function and
the maximum value and pass to the next level the value from the
calling function plus one.

Bob

Bob Calbridge = bcalb...@dcccd.edu
Senior Network Systems Programmer
Postmaster, Cook, Bottle Washer

Jeremy Carroll

unread,
Oct 31, 1996, 3:00:00 AM10/31/96
to

Lee Yen Hoe wrote:
> An array of size 4, with 1,2,3,4. I wanted to generate :
>
> 1
> 2
> 3
> 4
> 1,2
> 1,3
> 1,4
> 2,3
> 2,4
> 3,4
> 1,2,3
> 1,2,4
> 1,3,4
> 2,3,4
> 1,2,3,4
>

This is the power set (all subsets) problem, which can be modelled by
bitmaps one bit per element of the array.
Simple code for arrays with members fewer than the size of your machine
word is:

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int main( int argc , char ** argv ) {
int N; /* as in Yen Hoe's post */
unsigned int bitmask;
/* the ith bit of bitmask is 1 iff the ith element is in the subset */
int i;

N = atoi( argv[1] );
assert( N < 32 );

for ( bitmask = 0; bitmask < (1UL<<N); bitmask++) {
for (i=0; i<N; i++) {
if ( bitmask & (1<<i) ) {
printf("%d,",i);
}
}
printf("\n");
}
return 0;
}


It doesn't produce the output in the same order as you had it, and it
counts from 0 not 1. It also produces the blank line at the beginning.
If you don't want the blank line, start the first for loop at 1.

(My view not HP's).
--
Jeremy Carroll j...@hpl.hp.com
Hewlett Packard Labs VoiceMail +44 117 922 9051
Bristol tel/fax. +39 586 89 03 55

George

unread,
Oct 31, 1996, 3:00:00 AM10/31/96
to

Jens Andreasen <jens...@dsv.su.se> wrote:


> /* Print all combinations in a set of size n, recursive variant.
> */

> #include <stdio.h>
> #define N 4

> char a[N];

> void pr(int n){do if(a[n])printf(" %d",N-n);while(n--); puts("");}

> set(int n){

> if(n==N)return 1;

> a[n]=0;
> if(set(n+1))pr(n);
> a[n]=1;
> if(set(n+1))pr(n);
> return 0;
> }

> main(void){ set(0); return 0;}
^^^^
No no no no no....

G.


> /* ------------------------------------------------------------- */


> // Jens M Andreasen

> "Stay ahead of the competition, do their homework!"

....message ends.....

Marco Bravi

unread,
Nov 1, 1996, 3:00:00 AM11/1/96
to
Reply all
Reply to author
Forward
0 new messages