Построить все возможные упорядоченные комбинации из списка

Обновить

April 2019

Просмотры

138 раз

1

У меня есть список .Net и мне было интересно , что большинство (или « разумно » близко) эффективным способом было бы объединить их следующим образом:

С учетом того, как список 3 элемента ( «A», «B» и «C»), что я в основном нужно будет следующее быть возвращен из метода:

  1. A
  2. В
  3. С
  4. AB
  5. переменный ток
  6. До нашей эры
  7. азбука

В основном порядок элементов внутри должен оставаться неизменным (A> B> C), и, следовательно, только, например, 4) «AB» выше можно / должно быть возвращено, но наоборот ( «B A») нет.

Я возился с этим на некоторое время теперь, но я далек от элегантного кода в данный момент, но, возможно, кто-то сделал что-то подобное уже и знает, как сделать это правильно / эффективно.

2 ответы

0

Currently I assume that the order of return does not matter. I will return the elements in the following order:

1. A
2. B
3. A B
4. C
5. A C
6. B C
7 A B C

If this would not work for you please write back and I will try to figure out working algorithm.

This order might seem a bit weird to you but this is the straigt forward order you will receive if you iterate all possible combinations of the elements.

For every combination of elements I assign binary mask with 1s where you choose elements. Thus, A being the first bit, B the second, C the third bit (I am giving example with three elements, but this obviously scales even for more elements).

 A B -> 011 = 3
 C -> 100 = 4
 B C -> 110 = 6

I will give oyu pseudocode in C++ as I am not master of .Net, but I am fairly confident that you will be able to convert it to your language.

void printCombination(List<Element> elements, int mask) {
    int n = elements.size(); // number of elements
    for (int i = 0; i < n; i++) {
        bool elementPrinted = false;
        if (mask & (1 << i)) { //if the ith bit is set
           if (elementPrinted) cout << " "; // adding separator
           cout << elements.get(i);
           elementPrinted = true;
        }
        cout << "\n";
    }
}
void getAllCombinations(List<Element> elements) {
    int n = elements.size(); // number of elements
    for (int mask = 1; mask < (1 << n); mask++) { // iterate all possible submasks
        printCombination(elements, mask);
    }
}
1

There are three ways to generate such sets that I can think of:

Bit representation of elements You can iterate from 1 to 1 << length (exclusivley) and build lists from the set bits, in your example:

1   001   {A}
2   010   {B}
3   011   {A, B}
4   100   {C}
5   101   {A, C}
6   110   {B, C}
7   111   {A, B, C}

The list of lists is in itself ordered, when you do it the other way round, i.e. have the top bit represent A instead of the lowest bit.

Binary recursion Recurse on the elements of the list, where in each step you go down two paths: Include the current element or discard it. You will have to build a list as you recurse; when you have treated all elements of the original list, add it to the result.

This might be more efficient than building the list from bit patterns every time. It will also generate the empty list, which you should treat specially.

Fill in Start with 1 << length empty lists. Place the first element in all lists of the second half. Place the second element in all lists of the second and forth quarters. Place the third element in each list in the 2nd, 4th, 6th and 8th octants. And so on. This is really just the iterative variant of the recursive approach and will also create the empty list. (It also correlates with the bit-pattern solution.)