By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,557 Members | 1,406 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,557 IT Pros & Developers. It's quick & easy.

Programming C : combinations of n int from m sets

P: 4
Hi, I have a problem in finding a code to work out all possible combinations of n int (digits) from m sets; the number of sets is given in input the number of digits in each set may vary from 1 to n. For example:

s[1] = 1, 2, 8, 5
s[2] = 6,
s[3] = 10, 3

should produce:

combo1: 1 6 10
combo2: 1 6 3
combo3: 2 6 10
combo4: 2 6 3
combo5: 8 6 10
combo6: 8 6 3
combo7: 5 6 10
combo8; 5 6 3

combo: 1 2 6 is incorrect because it contains two digits from the same set;
combo: 1 10 is incorrect because each combo must contain as many digits as the number of sets.
So far I started with
Expand|Select|Wrap|Line Numbers
  1.  
  2. struct node{
  3. int id;
  4. struct succ}
  5.  
  6. struct succ{
  7. int val;
  8. struct succ *next;
  9. }
  10. struct node s[3]
  11.  
Then I got stuck. I'm new at C so I'd really appreciate some help. Tks!
Sep 13 '10 #1
Share this Question
Share on Google+
6 Replies


Expert 100+
P: 2,398
Foi each set-of-values, if N is the number of int values in the set then you need to keep track of N+1 data items. The "+1" comes from remembering the value N itself.

For the set-of-sets, if X is the number of sets then you need to keep track of X+1 data items.

By the way, line 4 is an illegal forward reference to line 6.
Sep 13 '10 #2

P: 4
so, I'll explain you the problem from the beginning...
the assignment gives me an array of lists,each single list is identified by an ID and contains some integer values which can't be repeated in the same combination.
The number of integer in each list can vary for example:

list[1] : 1, 2, 5
list[2]: 7, 8
list[3]: 9 , 13, 15, 17
list[1] contains 3 element , list[2] 2 elements and list[3] contains 4 elements

instead

list[1] : 1, 2, 5
list[2]: 2, 8
list[3]: 7, 3

is incorrect because 2 is repeated in two list

so I have two structures,
-one is the array containing the lists

Expand|Select|Wrap|Line Numbers
  1.  
  2.  
  3. #define N 3
  4.  
  5. struct arr{
  6. int ID;
  7. struct list *next;
  8. }
  9.  
  10. struct arr s[N];
  11.  
  12.  
and the other structure is the list for each ID...

Expand|Select|Wrap|Line Numbers
  1.  
  2. struct list{
  3. int value;
  4. struct list *next;}
  5.  
  6. struct list *start = NULL;   //pointer at the starting point of the list
  7.  
  8. s[1] = 1, 4, 6
  9. s[2] = 8, 2
  10. s[3] = 9 10, 13
  11.  

the purpose is to find all the combinations that contain N values , in each combination there must be one only integer from each list .
For example:

combination1 : 1, 8, 9 -----> OK
combination2 :4, 2, 10-----> OK
combination3 :6, 2, 13------->OK
combination4 :6, 2 ------->NO
combination5 :9 , 10, 2----->NO
combination6 :8------>NO
Sep 14 '10 #3

jkmyoung
Expert 100+
P: 2,057
I can think of multiple ways to do this. Pseudocode:
Algorithm 1: Recursive.
Expand|Select|Wrap|Line Numbers
  1. For each element of list 1 (call function)
  2. __for each element of list 2 (call function)
  3. ____for each element of list 3  (call function)
  4. ...
  5. ______output all elements gathered
  6.  


Algorithm 2: iterative
Multiply all sizes of arrays to give max value
Expand|Select|Wrap|Line Numbers
  1. for counter = 0 to max - 1{
  2.   i = counter
  3.   for each list {
  4.     size = size of list
  5.     choose element [i%size] in the list
  6.     i/= size
  7.   }
  8. }
  9.  
I personally prefer algorithm 2 due to less overhead.
Sep 14 '10 #4

P: 4
can you explain better what function you refer to in algorithm 1?I have thought off a function to combine element but I don't know if you refer to the same thing.

I can't use the second because the elements of each list are not numbered but you can refer to the next element of each list by using *next for example

Expand|Select|Wrap|Line Numbers
  1. list[1] = 1, 2, 5
  2. ...
  3.  
  4. list[i] = 1 , list[1]->next = 2
  5.  
  6.  
  7.  
Sep 14 '10 #5

jkmyoung
Expert 100+
P: 2,057
Store variables and recursively pass it to the next call of the function.
Roughly, It's something like:
Expand|Select|Wrap|Line Numbers
  1. function ( int listNumber, String sofar){
  2.   if (listNumber >= number of lists){
  3.     printOut sofar;
  4.     return
  5.   }
  6.   if listNumber != 0
  7.     soFar += ", ";
  8.   nextListNumber = listNumber + 1;
  9.  
  10.   foreach int element in list[listNumber]
  11.     call function(nextListNumber, soFar + element)  
  12. }
Initially you call function(0, "");
Sep 14 '10 #6

P: 4
i'll try it out and let you know if it works tomorrow morning;)tks a lot
Sep 14 '10 #7

Post your reply

Sign in to post your reply or Sign up for a free account.