Алгоритм возврата всех комбинаций k элементов из n

Question

Я хочу написать функцию, которая принимает массив букв в качестве аргумента и количество этих букв для выбора.

Допустим, вы предоставляете массив из 8 букв и хотите выбрать 3 буквы из этого. Тогда вы должны получить:

8! / ((8 - 3)! * 3!) = 56

Массивы (или слова) в ответ, состоящие из 3 букв.

Answer 1

Допустим, ваш массив букв выглядит так: «ABCDEFGH». У вас есть три индекса (i, j, k), указывающие, какие буквы вы собираетесь использовать для текущего слова. Вы начинаете с:

A B C D E F G H
^ ^ ^
i j k

Сначала вы меняете k, поэтому следующий шаг выглядит так:

A B C D E F G H
^ ^   ^
i j   k

Если вы достигли конца, вы продолжаете и меняете j, а затем снова k.

A B C D E F G H
^   ^ ^
i   j k

A B C D E F G H
^   ^   ^
i   j   k

Как только вы дойдете до G, вы также начнете менять меня.

A B C D E F G H
  ^ ^ ^
  i j k

A B C D E F G H
  ^ ^   ^
  i j   k
...

function initializePointers($cnt) {
    $pointers = [];

    for($i=0; $i<$cnt; $i++) {
        $pointers[] = $i;
    }

    return $pointers;     
}

function incrementPointers(&$pointers, &$arrLength) {
    for($i=0; $i<count($pointers); $i++) {
        $currentPointerIndex = count($pointers) - $i - 1;
        $currentPointer = $pointers[$currentPointerIndex];

        if($currentPointer < $arrLength - $i - 1) {
           ++$pointers[$currentPointerIndex];

           for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
                $pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
           }

           return true;
        }
    }

    return false;
}

function getDataByPointers(&$arr, &$pointers) {
    $data = [];

    for($i=0; $i<count($pointers); $i++) {
        $data[] = $arr[$pointers[$i]];
    }

    return $data;
}

function getCombinations($arr, $cnt)
{
    $len = count($arr);
    $result = [];
    $pointers = initializePointers($cnt);

    do {
        $result[] = getDataByPointers($arr, $pointers);
    } while(incrementPointers($pointers, count($arr)));

    return $result;
}

$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);

Основано на https://stackoverflow.com/a/127898/2628125,, но более абстрактно для указателей любого размера.

Answer 2

Вот мое предложение в C ++

Я пытался наложить как можно меньше ограничений на тип итератора, поэтому это решение предполагает только прямой итератор и может быть const_iterator. Это должно работать с любым стандартным контейнером. В случаях, когда аргументы не имеют смысла, он выдает std :: invalid_argumnent

#include <vector>
#include <stdexcept>

template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
    if(begin == end && combination_size > 0u)
        throw std::invalid_argument("empty set and positive combination size!");
    std::vector<std::vector<Fci> > result; // empty set of combinations
    if(combination_size == 0u) return result; // there is exactly one combination of
                                              // size 0 - emty set
    std::vector<Fci> current_combination;
    current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
                                                        // in my vector to store
                                                        // the end sentinel there.
                                                        // The code is cleaner thanks to that
    for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
    {
        current_combination.push_back(begin); // Construction of the first combination
    }
    // Since I assume the itarators support only incrementing, I have to iterate over
    // the set to get its size, which is expensive. Here I had to itrate anyway to  
    // produce the first cobination, so I use the loop to also check the size.
    if(current_combination.size() < combination_size)
        throw std::invalid_argument("combination size > set size!");
    result.push_back(current_combination); // Store the first combination in the results set
    current_combination.push_back(end); // Here I add mentioned earlier sentinel to
                                        // simplyfy rest of the code. If I did it 
                                        // earlier, previous statement would get ugly.
    while(true)
    {
        unsigned int i = combination_size;
        Fci tmp;                            // Thanks to the sentinel I can find first
        do                                  // iterator to change, simply by scaning
        {                                   // from right to left and looking for the
            tmp = current_combination[--i]; // first "bubble". The fact, that it's 
            ++tmp;                          // a forward iterator makes it ugly but I
        }                                   // can't help it.
        while(i > 0u && tmp == current_combination[i + 1u]);

        // Here is probably my most obfuscated expression.
        // Loop above looks for a "bubble". If there is no "bubble", that means, that
        // current_combination is the last combination, Expression in the if statement
        // below evaluates to true and the function exits returning result.
        // If the "bubble" is found however, the ststement below has a sideeffect of 
        // incrementing the first iterator to the left of the "bubble".
        if(++current_combination[i] == current_combination[i + 1u])
            return result;
        // Rest of the code sets posiotons of the rest of the iterstors
        // (if there are any), that are to the right of the incremented one,
        // to form next combination

        while(++i < combination_size)
        {
            current_combination[i] = current_combination[i - 1u];
            ++current_combination[i];
        }
        // Below is the ugly side of using the sentinel. Well it had to haave some 
        // disadvantage. Try without it.
        result.push_back(std::vector<Fci>(current_combination.begin(),
                                          current_combination.end() - 1));
    }
}

Answer 3

Все сказано и сделано, вот код O'caml для этого. Алгоритм очевиден из кода ..

let combi n lst =
    let rec comb l c =
        if( List.length c = n) then [c] else
        match l with
        [] -> []
        | (h::t) -> (combi t (h::c))@(combi t c)
    in
        combi lst []
;;

Answer 4

Вот метод, который дает вам все комбинации указанного размера из строки произвольной длины. Аналогично решению Кинмарса, но работает для различного ввода и k.

Код может быть изменен, чтобы обернуться, то есть 'dab' от ввода 'abcd' w k = 3.

public void run(String data, int howMany){
    choose(data, howMany, new StringBuffer(), 0);
}


//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
    if (result.length()==k){
        System.out.println(result.toString());
        return;
    }

    for (int i=startIndex; i<data.length(); i++){
        result.append(data.charAt(i));
        choose(data,k,result, i+1);
        result.setLength(result.length()-1);
    }
}

Вывод для "abcde":

abc abd abe acd ace ade bcd bce bde cde

Answer 5

Я создал для этого решение в SQL Server 2005 и разместил его на своем веб-сайте: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

Вот пример, показывающий использование:

SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')

Результаты:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)

Answer 6

Вот код, который я недавно написал на Java, который вычисляет и возвращает все комбинации элементов «num» из элементов «outOf».

// author: Sourabh Bhat (heySourabh@gmail.com)

public class Testing
{
    public static void main(String[] args)
    {

// Test case num = 5, outOf = 8.

        int num = 5;
        int outOf = 8;
        int[][] combinations = getCombinations(num, outOf);
        for (int i = 0; i < combinations.length; i++)
        {
            for (int j = 0; j < combinations[i].length; j++)
            {
                System.out.print(combinations[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] getCombinations(int num, int outOf)
    {
        int possibilities = get_nCr(outOf, num);
        int[][] combinations = new int[possibilities][num];
        int arrayPointer = 0;

        int[] counter = new int[num];

        for (int i = 0; i < num; i++)
        {
            counter[i] = i;
        }
        breakLoop: while (true)
        {
            // Initializing part
            for (int i = 1; i < num; i++)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;
            }

            // Testing part
            for (int i = 0; i < num; i++)
            {
                if (counter[i] < outOf)
                {
                    continue;
                } else
                {
                    break breakLoop;
                }
            }

            // Innermost part
            combinations[arrayPointer] = counter.clone();
            arrayPointer++;

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 1; i--)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i - 1]++;
            }
        }

        return combinations;
    }

    private static int get_nCr(int n, int r)
    {
        if(r > n)
        {
            throw new ArithmeticException("r is greater then n");
        }
        long numerator = 1;
        long denominator = 1;
        for (int i = n; i >= r + 1; i--)
        {
            numerator *= i;
        }
        for (int i = 2; i <= n - r; i++)
        {
            denominator *= i;
        }

        return (int) (numerator / denominator);
    }
}

Answer 7

Краткое решение Javascript:

Array.prototype.combine=function combine(k){    
    var toCombine=this;
    var last;
    function combi(n,comb){             
        var combs=[];
        for ( var x=0,y=comb.length;x<y;x++){
            for ( var l=0,m=toCombine.length;l<m;l++){      
                combs.push(comb[x]+toCombine[l]);           
            }
        }
        if (n<k-1){
            n++;
            combi(n,combs);
        } else{last=combs;}
    }
    combi(1,toCombine);
    return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);

Answer 8

Алгоритм:

• Количество от 1 до 2 ^ n.
• Преобразование каждой цифры в ее двоичное представление.
• Переведите каждый бит 'on' в элементы вашего набора на основе позиции.

В C #:

void Main()
{
    var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };

    var kElement = 2;

    for(var i = 1; i < Math.Pow(2, set.Length); i++) {
        var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
        var cnt = Regex.Matches(Regex.Escape(result),  "1").Count; 
        if (cnt == kElement) {
            for(int j = 0; j < set.Length; j++)
                if ( Char.GetNumericValue(result[j]) == 1)
                    Console.Write(set[j]);
            Console.WriteLine();
        }
    }
}

Почему это работает?

Существует биекция между подмножествами n-элементного набора и n-битных последовательностей.

Это означает, что мы можем выяснить, сколько существует подмножеств путем подсчета последовательностей.

например, четыре элемента, представленные ниже, могут быть представлены {0,1} X {0, 1} X {0, 1} X {0, 1} (или 2 ^ 4) различными последовательностями.

Итак - все, что нам нужно сделать, это сосчитать от 1 до 2 ^ n, чтобы найти все комбинации. (Мы игнорируем пустое множество.) Затем переведите цифры в их двоичное представление. Затем замените элементы вашего набора на «включенные» биты.

Если вы хотите получить только k элементов, выведите их только тогда, когда k битов включены.

(Если вы хотите, чтобы все подмножества вместо k подмножеств длины, удалите часть cnt / kElement.)

(в качестве доказательства см. Бесплатное программное обеспечение MIT по математике для информатики, Lehman et al., Раздел 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/)

Answer 9

Я написал класс для работы с общими функциями для работы с биномиальным коэффициентом, к которому относится ваша проблема. Он выполняет следующие задачи:

1. Выводит все K-индексы в хорошем формате для любого N, выбирающего K, в файл. K-индексы могут быть заменены более описательными строками или буквами. Этот метод делает решение проблемы такого типа довольно тривиальным.

2. Преобразует K-индексы в соответствующий индекс записи в отсортированной таблице биномиальных коэффициентов. Этот метод намного быстрее, чем старые опубликованные методы, основанные на итерации. Это делается с помощью математического свойства, присущего треугольнику Паскаля. Моя газета говорит об этом. Я считаю, что я первый, кто открыл и опубликовал эту технику, но я могу ошибаться.

3. Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы.

4. Использует Mark Dominus метод для вычисления биномиального коэффициента, который с гораздо меньшей вероятностью переполняется и работает с большими числами.

5. Класс написан на .NET C # и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое при значении true создаст общий список для хранения управляемых объектов. Если это значение равно false, таблица не будет создана. Таблицу не нужно создавать для выполнения 4 вышеуказанных методов. Методы доступа предоставляются для доступа к таблице.

6. Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован с 2 случаями, и никаких известных ошибок нет.

Чтобы прочитать об этом классе и загрузить код, см. Таблицу биномиального коэффициента .

Нетрудно преобразовать этот класс в C ++.

Answer 10

Вот мое решение Scala :

def combinations[A](s: List[A], k: Int): List[List[A]] = 
  if (k > s.length) Nil
  else if (k == 1) s.map(List(_))
  else combinations(s.tail, k - 1).map(s.head :: _) ::: combinations(s.tail, k)