Быстрый способ получения r-длинных комбинаций множества A, которые имеют хотя бы один элемент из множества B, который является подмножеством A

Question

Например, если A={0,1,2,3,4}, r=3 а также B={1,4}результат будет:

[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

Вот и все r-длинные комбинации А, кроме [0, 2, 3]потому что тот не содержит ни 1, ни 4.

В настоящее время у меня есть решение, использующее самый быстрый алгоритм получения нормальных из известных мне комбинаций, и просто проверяю, содержат ли сгенерированные комбинации элемент B (java):

    int[] A = new int[]{0,1,2,3,4};
    int[] B = new int[]{1,4};
    int n = A.length;
    int r = 3;

    int[] picks = new int[r]; //Holds indexes of elements in A
    for (int i = 0; i < picks.length; i++)
        picks[i] = i;

    int lastindex = picks.length - 1;

    outer:
    while (true) {
        int at = lastindex;
        while (true) {
            picks[at] += 1;
            if (picks[at] < n) {
                int displacement = picks[at] - at; // at + displacement = picks[at], at + displacement + 1 = picks[at] + 1 ,...

                // Make all picks elements after at y = picks[at] + x, so picks={0, 2, 4, 6, 18, 30} & at=3 --> picks={0, 2, 4, 5, 6, 7}
                // (Note that this example will never take place in reality, because the 18 or the 30 would be increased instead, depending on what n is)

                // Do the last one first, because that one is going to be the biggest,
                picks[lastindex] = lastindex + displacement;
                if (picks[lastindex] < n) { // and check if it doesn't overflow
                    for (int i = at + 1; i < lastindex; i++)
                        picks[i] = i + displacement;

                    int[] combination = new int[r];
                    for (int i = 0; i < r; i++)
                        combination[i] = A[picks[i]];
                    System.out.print(Arrays.toString(combination));
                    //^With this, all r-long combinations of A get printed

                    //Straightforward, bruteforce-ish way of checking if int[] combination
                    //contains any element from B
                    presence:
                    for (int p : combination) {
                        for (int b : B) {
                            if (p==b) {
                                System.out.print(" <-- Also contains an element from B");
                                break presence;
                            }
                        }
                    }

                    System.out.println();

                    break;
                }
            }
            at--;
            if (at < 0) {
                //Moving this check to the start of the while loop will make this natively support pick 0 cases (5C0 for example),
                //but reduce performance by I believe quite a bit. Probably better to special-case those (I haven't
                // done that in this test tho)
                break outer;
            }
        }
    }

выход:

[0, 1, 3] <-- Also contains an element from B
[0, 1, 4] <-- Also contains an element from B
[0, 2, 3]
[0, 2, 4] <-- Also contains an element from B
[0, 3, 4] <-- Also contains an element from B
[1, 2, 3] <-- Also contains an element from B
[1, 2, 4] <-- Also contains an element from B
[1, 3, 4] <-- Also contains an element from B
[2, 3, 4] <-- Also contains an element from B

Как написано в комментариях, я считаю этот метод очень элементарным. Кто-нибудь может придумать более быстрый способ сделать это?

Answer 1

Если у вас есть int[][] FindCombinations(int[] set, int length) функция, которая возвращает список всех lengthдлинные комбинации setвыполните следующие действия (псевдокод):

for i=1 to B.length
{
  int bi = B[i];

  A = A - bi; // remove bi from A
  foreach C in FindCombinations(A, r-1)
  {
     output C+bi // output the union of C and {bi}
  }
}

Таким образом, все комбинации содержат по крайней мере один элемент из B (и могут также содержать элементы B, которые еще не использовались) без особой дополнительной работы. Все другие комбинации исключаются бесплатно (их вообще не нужно искать), а также исключается проверка, что комбинация содержит элемент из B для каждой комбинации.

Будет ли этот алгоритм более быстрым, во многом зависит от того, насколько эффективно вы можете добавлять / удалять элементы из набора и процент включенных против исключенных комбинаций (т.е. если вы в конечном итоге исключаете только 1% от общего числа комбинаций, это, вероятно, не стоит)

Обратите внимание, что при получении комбинаций для объединения с {b[i]} они также могут содержать элемент B[j], где j>i. Когда вы дошли до того, что получили комбинации для объединения с B[j], ни одна из них не будет содержать B[i], поэтому все комбинации уникальны.