Combinations of n objects from n groups

[SanJuanWolf]

I am fairly new at programming in C and I'm having problems with writing a program which combines n objects from n different groups and prints them; for example objects a1 a2 a3from group A with b1 b2 b3 from group B and c1 c2 from group C; both group number and objects number may vary; the final possible combinations must contain 1 object from each group at the time (for example a1 b3 c2 is ok, but a1 a2 b3 is wrong because there are two objects from the same group and none from the third group). So far I've made several attempts using lists, rb trees, etc but I don't seem to be getting anywhere. So I'd really appreciate some help.... Thanks

[Adak]

Think of it like three wheels on an old fashioned car odometer. Each wheel is from a different group, and each wheel can spin around, and then go back to it's starting value.

Three nested for loops is the simplest implementation I know. Arrays are what I use, for each group. Any data structure should be OK, but I like arrays for their simplicity and speed.

To see every possible combination, just have the right most wheel as your "driver" wheel, and when it has gone through all it's possible values, then it "kicks" the wheel immediately to it's left, over by one value. Just like a real odometer worked.

[SanJuanWolf]

Think of it like three wheels on an old fashioned car odometer. Each wheel is from a different group, and each wheel can spin around, and then go back to it's starting value.

Three nested for loops is the simplest implementation I know. Arrays are what I use, for each group. Any data structure should be OK, but I like arrays for their simplicity and speed.

To see every possible combination, just have the right most wheel as your "driver" wheel, and when it has gone through all it's possible values, then it "kicks" the wheel immediately to it's left, over by one value. Just like a real odometer worked.

The problem is that the number of the groups is given in input (say for example 3 or 4, etc) but the number of objects in each group may vary(for example group A may contain 3 objects, group B may contain 2 objects, group C may contain 1 object) therefore I can't work on arrays. Let's take for example:

A - a1 a2 a3
B - b1
C - c1 c2

the output should be 6 possible combinations:

comb1: a1 b1 c1 comb2: a1 b1 c2 comb3: a2 b1 c1 comb3: a2 b1 c2
comb4: a3 b1 c1 comb5: a3 b1 c2

The position of the objects in output is irrelevant it can be: a1 b1 c1 or b1 a1 c1, etc.- what is important is that in each combination the number of objects has to be the same as the number of the groups.

[Adak]

That's not a logical problem - think of your odometer wheels again. Imagine that instead of each wheel having 10 digits (0-9), that the right most wheel of the three (which is the one I use as the "driver" wheel), has only two digits, 1 and 2. And the middle wheel has but a single digit: 1, while the left most wheel (the A set), has 3 digits: 1,2,3.

Use you nested for loops again, but you don't need a for loop for the middle wheel, because it only has one value. So you're down to an ez two for loops.

I've used this several times, it works just fine. If you set the wheels up with their arrays being sorted to start with, and having their start values be the lowest value possible, then the output will be in sorted order.

Note that a1, b1, c1 is repeated in your post. That indicates a refinement of logic is needed in your loops. After the c wheel has generated c2, the next increment for it should be back to c1, and the a wheel should be advanced to the next value.

[SanJuanWolf]

That's not a logical problem - think of your odometer wheels again. Imagine that instead of each wheel having 10 digits (0-9), that the right most wheel of the three (which is the one I use as the "driver" wheel), has only two digits, 1 and 2. And the middle wheel has but a single digit: 1, while the left most wheel (the A set), has 3 digits: 1,2,3.

Use you nested for loops again, but you don't need a for loop for the middle wheel, because it only has one value. So you're down to an ez two for loops.

I've used this several times, it works just fine. If you set the wheels up with their arrays being sorted to start with, and having their start values be the lowest value possible, then the output will be in sorted order.

Note that a1, b1, c1 is repeated in your post. That indicates a refinement of logic is needed in your loops. After the c wheel has generated c2, the next increment for it should be back to c1, and the a wheel should be advanced to the next value.

I get the reasoning but when I get down to the code I get entangled, besides maybe my example was not correctly set out. In my problem the objects are (int), thus so far the situation is the following:

struct node{
int id;
struct succ}

struct succ{
int val;
struct succ *next;
}
struct node s[3]

s[1] = 1, 2, 8, 4, 5
s[2] = 6, 7, 11, 9
s[3] = 10, 3

my trouble is to get all combinations containing 3 not-repeated objects/int of the given sets (for example comb1: 1 6 10 - comb2: 1 7 10 and so on)

[Adak]

The data type is irrelevant. You can do what I suggested with any data type. It's a matter of logic.

1) You can't have s[1] = 1, 2, 8, etc. s[1] is the element in s[] right next to s[0] and s[2], and can hold just one integer, not five.

You could call the arrays s1[], s2[], and s3[] however. That would be fine.

2) You need the include file stdio.h. You don't need a node or a struct, so you can delete them.

You need a main(), and the the three nested for loops - one for each "wheel". (data set)

3) Always use the code tags around your program on the forum. Otherwise, the program gets smashed over to the left hand side, in a very bad font to study, like it's html text. Just click on the [code] icon at the top of the advanced editor window, and then paste your code between those provided tags.

If you think it won't work, consider that your car's odometer displays every single possible mile combination: thousands, hundreds, tens, ones and tenths, on your car. That's all we're doing here - building a virtual odometer, but we're changing the digits to be the numbers in the set that that wheel, is representing.

[SanJuanWolf]

Sorry about the code issue. Thanks for your answer, I'll try and see if I can work out a solution basing on your ideas. Will let you know in case I can make it.

[abhimanipal]

@SanJuanWolf
Who decided the number of groups ?

@Adak
Quick question. How do you plan to implement nested loops when the number of groups is a variable

I have a dirty solution which may work in this scenario but I am hoping Adak can make that unnecessary

[Adak]

Whatever the constraints are, they'll have to have logic to handle it. Nothing magical about nested for loops, they're just a good simple way, to handle creating combinations.

The more difficult the problem, the more likely the logic will need to move to a more representative design, and at the same time, have more low level variables.

Basically, although the nested loop is there, it doesn't mean it has to be entered into, (looped through), for any combination. The logic has to determine which for loops will have their loop bodies executed.

Your solution idea may be better than mine, Abhimanipal. I am hoping that the OP will look back in his class notes or book, and see what it is that the instructor wants him to use, in this case. Seems like a very difficult problem to just toss out to a student, without some lecture or written assistance.

[SanJuanWolf]

The number of groups is given in the assignement. Unfortunately the instructor gave us just few very simple examples of C programs, which are useless to work out the function I need, well, yes, the problem was tossed out onto us just like that, with no other clue, just the expected output.
Anyhow first I had to build a data structure (which I have done) and work on that, so basically what I have to do now is to find an algorithm which makes the program find all combinations starting from the array of lists, the way I wrote them down.

[Adak]

I've seen code for this (what language I'm not sure), last year, when I was doing some looking around on google for Permutations and combinations.

I can't imagine why you'd want to build a data structure, before you had an algorithm. Or why you'd want to use an array of lists.

I guess you know what you're doing - good luck.

[abhimanipal]

If the number of groups will always be the same then use the nested loops logic suggested by Adak

[SanJuanWolf]

I've seen code for this (what language I'm not sure), last year, when I was doing some looking around on google for Permutations and combinations.

I can't imagine why you'd want to build a data structure, before you had an algorithm. Or why you'd want to use an array of lists.

I guess you know what you're doing - good luck.

The reason for I MUST use a BUILT BEFORE data structure is that the instructor set the rules of the task; as far as the array of lists I chose it because I've got to combine n groups of k number of elements (as I said k being variable does not allow me to use arrays of arrays...).
By the way I think the code you saw was python which is not so easily transformed into C. I suppose I'll keep on trying with nested loops although I've got the feeling of just looping around... Tks all the same.

[Adak]

see. I thought you were just being ornery.

My idea was to use small separate arrays, one for each group.

If you have experience working with an array of linked lists, you're programming skill is beyond mine. I've never worked with such an array, nor have I seen code for such, although of course, I know they are used.

I will think on your problem.

[Adak]

OK, this is one way I was looking at it. I did this with arrays, BUT there's no reason why the array could not be replaced (index by the depth of the linked list).

Three groups, with my choices being to show 3 values from group1 (Alpha), 3 values from group2 (even), and 1 value from group3 (odd).

Output is:

abcdef <= alpha group
02468  <= even group
13579  <= odd group

 Enter the number of items to be shown from alpha group: 3
 Enter the number of items to be shown from the even group: 3
 Enter the number of items to be shown from the odd group: 1


groups:
  One Two Three (alpha, even, odd)
================
  a   0   1
  a   2   1
  a   4   1
  b   0   1
  b   2   1
  b   4   1
  c   0   1
  c   2   1
  c   4   1

			     press enter when ready

Is that somewhat close to what you want for output of your program?

[SanJuanWolf]

yes of course it is similar...but in my assignment they don't ask you to insert the number of items that must be shown and I must find ALL the combination containing three items, one from each list so it's a little bit different I think...but if you want ,you can send me the code you use that I think it would be very very very useful ..tks a lot

[Adak]

This is the program:

#include <stdio.h>

int main() {
  int i, j, k, temp, alpha1, odd1, even1; 
  char alpha[]="abcdef";
  char even[]="02468";
  char odd[]="13579";

  printf("\nThree Groups:\n %s <==alpha\n %s  <==odd\n %s  <==even",\
   alpha, odd, even );
  printf("\n\n Enter the number of items to be shown from alpha group: ");
  scanf("%d", &alpha1);
  getchar();
  printf("\n Enter the number of items to be shown from the even group: ");
  scanf("%d", &even1);
  getchar();
  printf("\n Enter the number of items to be shown from the odd group: ");
  scanf("%d", &odd1);
  getchar();
  printf("\n One Two Three:\n==============");
  for(i=0;i<alpha1;i++) {
    //printf("%3c", alpha[i]);
    
    for(j=0;j<even1;j++) {
      //printf("\t\t%3c", even[j]);
      
      for(k=0;k<odd1;k++) {
        printf("\n%3c %3c %3c", alpha[i], even[j], odd[k]);

      }
    }
  }
  printf("\n\n\t\t\t     press enter when ready");

  i = getchar(); ++i;
  return 0;
}

I was wondering if some boolean type switches or flags could be added to control the printing of the wheels, according to the requirements of the assignment.

[Adak]

Yes, the switch/flag idea works.

[rishabhsetia65]

3f156ec468ac1b2ac289dfa4fc03187a

[Airshow]

Hi guys,

I guess this problem is still live, though it's a month old now.

I'm in a part of Damiweb here where I don't normall go. You will generally find me in the JavaScript / DHTML / AJAX forum.

The good news
I have a general solution for "n objects from n groups".

As should be clear, nested loops are only good for "n objects from a known number of groups".

The answer is to have just one loop to visit elements at the each level, and to use RECURSION inside the loop to visit the other groups. Recursion is where a function calls itself.

The bad news
I have never written a line of C in my life, so here it is as a web page, with the code in JavaScript.

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html>
<head>
<title>Airshow :: Untitled</title>
<style type="text/css">
body {  }
div.combination {
	width: 140px;
	border-bottom: 1px solid #999;
	font-family: verdana;
	font-size: 10pt;
}
</style>

<script>
//First shape the data as an array of arrays
var groups = [
//	['A', 'B'],//Uncomment this line for four goups. No other changes necessary.
	['a','b','c','d','e','f'],
	['0','2','4','6','8'],
	['1','3','5','7','9']
]
var count = 0;//line counter (just to let us know how many cominations we have generated)
var separator = ' - ';//whatever you want to format the printed combinations.
function printCombinations(level, a1) {
	if(level == 0 ) { a1 = []; }//starter array at level 0
	var a2, i, div;
	for( i=0; i<groups[level].length; i++ ) {//visit each array element at this level
		a2 = a1.concat( [groups[level][i]] );//for efficiency (in javascript), we accumulate the result in an array, not a string.
		if( groups[level+1] ) {//if another level exists
			printCombinations(level+1, a2);//make RECURSIVE call to visit next level, passing cumulative result for this combination thus far.
		}
		else {//this block simply handles the output when level is as high as it can legally get.
		//Because we are inserting the the DOM, it is a bit longwinded
			div = document.createElement('div');//create DOM element
			div.className = 'combination';//apply a style
			div.innerHTML = (++count).pad(3).bold() + ': ' + a2.join(separator);//concatenate the cumulative combination and format with separator
			document.getElementById('results').appendChild(div);//insert in the DOM
		}
	}
}
Number.prototype.pad = function(n) {//a little formatting utility to make all results an equal length
	var i, a = [this];
	for(i=0; i<n; i++) {
		if( this < Math.pow(10, i) ) { a.unshift(0); }//add a leading "0"
	}
	return a.join('');//return string of this (number) padded with leading zeros to make length n.
}
</script>
</head>

<body>

<button onclick="printCombinations(0)">Go</button>
<div id="results"></div>

</body>
</html>

All you need now is to translate all this into C!!!!! Easy|difficult; I have no idea.

Good luck

Airshow