C++

Forum

 
Combinatorics algorithm for pairing

JockX (293)
This is more a general algorithms questrion than strictly C++. I guess the answer is a simple nested loop, but it really eludes me when I try to think of it.
This is the problem - I have a list of elements and I want to get all possible ways in which I can assign a pair to each of the elements from the same list:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
List<Element> = {A, B, C}; // this is what I have

// And this is what I want to get from the function:
List<Map<Element, Element>> =
{
  {A->A, B->A, C->A}, {A->A, B->A, C->B}, {A->A, B->A, C->C},
  {A->A, B->B, C->A}, {A->A, B->B, C->B}, {A->A, B->B, C->C},
  {A->A, B->C, C->A}, {A->A, B->C, C->B}, {A->A, B->C, C->C},
  {A->B, B->A, C->A}, {A->B, B->A, C->B}, {A->B, B->A, C->C},
  {A->B, B->B, C->A}, {A->B, B->B, C->B}, {A->B, B->B, C->C},
  {A->B, B->C, C->A}, {A->B, B->C, C->B}, {A->B, B->C, C->C},
  {A->C, B->A, C->A}, {A->C, B->A, C->B}, {A->C, B->A, C->C},
  {A->C, B->B, C->A}, {A->C, B->B, C->B}, {A->C, B->B, C->C},
  {A->C, B->C, C->A}, {A->C, B->C, C->B}, {A->C, B->C, C->C}
};

Any helpful insights? I know it's easy - I just cannot see it :)
Last edited on
helios (17506)
Something simple:
1
2
3
4
5
 
List<Element> elements = {A, B, C};
List<Map<Element, Element>> list;
for (unsigned i = 0; i < 3*3*3; i++){
    list.append({A->elements[i/(3*3)], B->elements[i/3%3], C->elements[i%3]});
}
In general, when you have a list of symbols {x0, x1, ..., x(n-1)} and you need to generate the sequence of m-tuples
(x0, ..., x0, x0),
(x0, ..., x0, x1),
...,
(x0, ..., x0, x(n - 1)),
(x0, ..., x1, x0),
...,
(x(n-1), ..., x(n-1), x(n-1))
you can do it by iterating i from 0 to nm-1 and generating (x(i/nm - 1 % n), x(i/nm - 2 % n), ..., x(i/nm - (m - 1) % n), x(i/nm - m % n)).
Last edited on
JockX (293)
That's it. Thanks a lot!
Topic archived. No new replies allowed.