How to make possible combinations between elements of sets?

Make a chain long in the number of sets, each of which includes one element from each set. All sets are integer and the values ​​of the elements of the sets are in order (0, 1, 2, etc.)

enum ПЕРВАЯ { А1, А2 }; enum ВТОРАЯ { Б1, Б2 }; enum ТРЕТЬЯ { В1, В2, В3 }; Чтобы получилось так: А1 - Б1 - В1 А1 - Б1 - В2 А1 - Б1 - В3 А1 - Б2 - В1 А1 - Б2 - В2 А1 - Б2 - В3 А2 - Б1 - В1 А2 - Б1 - В2 А2 - Б1 - В3 А2 - Б2 - В1 А2 - Б2 - В2 А2 - Б2 - В3 // Допустим данные по всем enum хранятся так struct МНОЖЕСТВО { int первый; int последний; }; std::vector<МНОЖЕСТВО> вектор; вектор.resize(3); // ПЕРВАЯ вектор[0].первый = (int)ПЕРВАЯ::А1; вектор[0].последний = (int)ПЕРВАЯ::А2; // ВТОРАЯ вектор[1].первый = (int)ВТОРАЯ::Б1; вектор[1].последний = (int)ВТОРАЯ::Б2; // ТРЕТЬЯ вектор[2].первый = (int)ТРЕТЬЯ::В1; вектор[2].последний = (int)ТРЕТЬЯ::В3;

How can I get all the combinations?

Without 1C style. It works only for sets, where all elements are strictly in order.

 struct enum_maker { struct enum_class { int first; int last; std::string name; }; std::vector<enum_class> tree; void add_enum(int first, int last , std::string name) { enum_class enum_ob; enum_ob.first = first; enum_ob.last = last; enum_ob.name = name; tree.push_back(enum_ob); } void build_tree() { int iterations = 1; int enums = tree.size(); std::vector<std::vector<int>> matrix; matrix.resize(enums); std::vector<int> elements_in_enum; for(int i = 0; i < tree.size(); i++) { elements_in_enum.push_back((tree[i].last - tree[i].first)+1); iterations *= elements_in_enum[i]; } int special_A = iterations; // заполняем матрицу for(int i = 0; i < tree.size(); i++) { special_A = special_A / elements_in_enum[i]; int count_elements=0; int current_enum_element = tree[i].first; for(int j = 0; j < iterations; j++) { if(count_elements == special_A){current_enum_element++; if(current_enum_element>tree[i].last) { current_enum_element=tree[i].first; } count_elements=0; } count_elements++; matrix[i].push_back(current_enum_element); } } for(int i = 0; i < tree.size(); i++) { std::cout << "\n\n\n#### I=" << tree[i].name; for(int j = 0; j < matrix[i].size(); j++) { std::cout << "\nj=" << matrix[i][j] ; } } for(int i = 0; i < matrix[0].size(); i++) { std::string pairs; for(int j = 0; j < tree.size(); j++) { pairs += "[" + std::to_string( matrix[j][i]) + "]"; } std::cout << "\npairs=" << pairs; } } }; enum FIRST {A1,A2,A3,A4}; enum SECOND {B1,B2}; enum THIRD {C1,C2,C3}; int main() { enum_maker enum_maker_; enum_maker_.add_enum(FIRST::A1 , FIRST::A4 , "FIRST"); enum_maker_.add_enum(SECOND::B1 , SECOND::B2, "SECOND"); enum_maker_.add_enum(THIRD::C1 , THIRD::C3, "THIRD"); enum_maker_.build_tree(); std::system("pause"); }
  • one
    I hope this is pseudocode, and not so severe 1C style :) - Zowie
  • Read the 4th volume of the Knut - renegator
  • it seems that in this case a simple multiplication of sets will help the person. In the code - just a series of nested loops. That's just in the c / s ++ with enum there is a small problem - their size is not stored, you will have to add all sorts of "last_elem". - KoVadim
  • one
    If the number of sets is set in advance (let it be N ), use N nested loops. If not, do this: 1. Start the set of current elements, one by one into a set 2. Cycle: 3. Current set: = first 4. Advance the current element of the current set. 5. If at the same time you have rested against the maximum, reset the current element of the current set to the initial value and advance the number of the current set; if at the same time they are also rested against the maximum, it is ready, otherwise return to step 4. 6. Process the current combination, the end of the loop iteration is VladD
  • @manking, but you can clarify so I understand. for example, A1 and A2 are subsets of the FIRST set. you need to get all combinations of subsets from FIRST, SECOND and THIRD. Or some other combination is needed? - perfect

2 answers 2

Number of sets 3 or indefinite? I think it can be done as follows, using a two-dimensional matrix. 1) calculate the number of possible iterations as the product of the number of elements in in all the sets. In your case, 2 2 3 = 12. So the matrix will be 12X number of sets = 12x3.

2) We write in the first column the value A1 12/2 times and A2 also 6 times. will get

 [A1, 0, 0] ... 4 раза то же самое [A1, 0, 0] [A2, 0, 0] ... 4 раза то же самое [A2, 0, 0]

Further, the second column, in a cycle two times in the same way, that is, we alternate 12/2/2 = three times (where the first 2 is the number in the first set, the second 2 in the second). We obtain b1, b1, b1, b2, b2, b2, b1, b1, b1, b2, b2, b2.

 [A1, B1, 0] [A1, B1, 0] [A1, B1, 0] [A1, B2, 0] [A1, B2, 0] [A1, B2, 0] [A2, B1, 0] [A2, B1, 0] [A2, B1, 0] [A2, B2, 0] [A2, B2, 0] [A2, B2, 0]

In the same way we find that the third set must be taken 12/2/2/3 = 1 times. We get:

 [A1, B1, С1] [A1, B1, С2] [A1, B1, С3] [A1, B2, С1] [A1, B2, С2] [A1, B2, С3] [A2, B1, С1] [A2, B1, С2] [A2, B1, С3] [A2, B2, С1] [A2, B2, С2] [A2, B2, С3]

We have all the options, you can with any number of elements and sets. From the matrix is ​​not hard to overtake in the vector. I understand correctly, you need to get it?

  • Yes, the algorithm is fully working. Wrote the implementation. It seems to be working. Added to the question. - manking
  • one
    I am glad that it came, for I figured on the move and could blunder somewhere =) - spirit

This is a variable base number system.

  • We learn the number of combinations as the product of the sizes of sets
  • We iterate over all combinations, where the number of the combination identifies the number of the element in each set.

Implementation on javascript'e (it’s easy to rewrite, I think, will be easy):

 // Каждое множество - разряд системы счисления, // для примера десятичная CC var m = [ [0,1,2,3,4,5,6,7,8,9], [0,1,2,3,4,5,6,7,8,9], [0,1,2,3,4,5,6,7,8,9] ]; var mc = 1; // Число комбинаций for (var i=0;i<m.length;i++){ mc*=m[i].length; } var r = []; // Массив всех комбинаций for (var j=0;j<mc;j++){ // Номер текущей комбинации var cr = []; // Текущая комбинация var nc = 1; // Сдвиг разрядов for (var i=0;i<m.length;i++){ // Бежим по множествам var shifted = Math.floor(j / nc); // Номер комбинации, // сдвинутый на i разрядов влево. // Аналог для двоичной системы <<i var idx = shifted % m[i].length; // Индекс элемента в i-том разряде cr.push(m[i][idx]); // Заносим в комбинацию элемент по полученному индексу nc *= m[i].length; // Двигаем разряд влево дальше } r.push(cr); // Заносим комбинацию в массив }

Jsfiddle