Programming C : combinations of n int from m sets

[SanJuanWolf89]

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

 
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!

[donbock]

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.

[SanJuanWolf89]

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

#define N 3

struct arr{
int ID;
struct list *next;
}

struct arr s[N];

and the other structure is the list for each ID...

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

[jkmyoung]

I can think of multiple ways to do this. Pseudocode:
Algorithm 1: Recursive.

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

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.

[SanJuanWolf89]

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

list[1] = 1, 2, 5
...

list[i] = 1 , list[1]->next = 2

[jkmyoung]

Store variables and recursively pass it to the next call of the function.
Roughly, It's something like:

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, "");

[SanJuanWolf89]

i'll try it out and let you know if it works tomorrow morning;)tks a lot