429,557 Members | 1,406 Online
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   struct node{ int id; struct succ}   struct succ{ int val; struct succ *next; } struct node s[3]   Then I got stuck. I'm new at C so I'd really appreciate some help. Tks! Sep 13 '10 #1
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     #define N 3   struct arr{ int ID; struct list *next; }   struct arr s[N];     and the other structure is the list for each ID... Expand|Select|Wrap|Line Numbers   struct list{ int value; struct list *next;}   struct list *start = NULL;   //pointer at the starting point of the list   s[1] = 1, 4, 6 s[2] = 8, 2 s[3] = 9 10, 13   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

 Expert 100+ P: 2,057 I can think of multiple ways to do this. Pseudocode: Algorithm 1: Recursive. Expand|Select|Wrap|Line Numbers For each element of list 1 (call function) __for each element of list 2 (call function) ____for each element of list 3  (call function) ... ______output all elements gathered   Algorithm 2: iterative Multiply all sizes of arrays to give max value Expand|Select|Wrap|Line Numbers for counter = 0 to max - 1{   i = counter   for each list {     size = size of list     choose element [i%size] in the list     i/= size   } }   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 list[1] = 1, 2, 5 ...   list[i] = 1 , list[1]->next = 2       Sep 14 '10 #5

 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 function ( int listNumber, String sofar){   if (listNumber >= number of lists){     printOut sofar;     return   }   if listNumber != 0     soFar += ", ";   nextListNumber = listNumber + 1;     foreach int element in list[listNumber]     call function(nextListNumber, soFar + element)   } 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