Как найти перестановки размера N с неперемещенными объектами из списка с повторяющимися объектами? [Дубликат]

Допустим, ваш массив букв выглядит так: «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 , но более абстрактным для любого размера указателей.

Версия Clojure:

(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))

Я нашел эту тему полезной и подумал, что добавлю Javascript-решение, которое вы можете вставить в Firebug.

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
        string_recurse(active, rest.substring(1, rest.length));
    }
}
string_recurse("", "abc");

Выход должен быть следующим:

abc
ab
ac
a
bc
b
c

Краткий пример в Python:

def comb(sofar, rest, n):
    if n == 0:
        print sofar
    else:
        for i in range(len(rest)):
            comb(sofar + rest[i], rest[i+1:], n-1)

>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde

Для объяснения рекурсивный метод описан в следующем примере:

Пример: ABCDE Все комбинации из 3 будут:

• A со всеми комбинациями 2 из остальных (BCDE)
• B со всеми комбинациями 2 из остальных (CDE)
• C со всеми комбинациями из 2 от остальных (DE)

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}

Все сказанное и сделанное здесь для этого код 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 []
;;

Вот элегантная, общая реализация в Scala, как описано в 99 Scala Problems .

object P26 {
  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
    }

  def combinations[A](n: Int, ls: List[A]): List[List[A]] =
    if (n == 0) List(Nil)
    else flatMapSublists(ls) { sl =>
      combinations(n - 1, sl.tail) map {sl.head :: _}
    }
}

Прыжки на подножку и публикация другого решения. Это общая реализация Java. Вход: (int k) - количество элементов для выбора, а (List<T> list) - список, на который нужно выбрать. Возвращает список комбинаций (List<List<T>>).

public static <T> List<List<T>> getCombinations(int k, List<T> list) {
    List<List<T>> combinations = new ArrayList<List<T>>();
    if (k == 0) {
        combinations.add(new ArrayList<T>());
        return combinations;
    }
    for (int i = 0; i < list.size(); i++) {
        T element = list.get(i);
        List<T> rest = getSublist(list, i+1);
        for (List<T> previous : getCombinations(k-1, rest)) {
            previous.add(element);
            combinations.add(previous);
        }
    }
    return combinations;
}

public static <T> List<T> getSublist(List<T> list, int i) {
    List<T> sublist = new ArrayList<T>();
    for (int j = i; j < list.size(); j++) {
        sublist.add(list.get(j));
    }
    return sublist;
}

Краткое java-решение:

import java.util.Arrays;

public class Combination {
    public static void main(String[] args){
        String[] arr = {"A","B","C","D","E","F"};
        combinations2(arr, 3, 0, new String[3]);
    }

    static void combinations2(String[] arr, int len, int startPosition, String[] result){
        if (len == 0){
            System.out.println(Arrays.toString(result));
            return;
        }       
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len-1, i+1, result);
        }
    }       
}

Результат будет

[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]

Вот код, который я недавно написал на 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);
    }
}

Алгоритм:

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

В 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, чтобы найти все комбинации. (Мы игнорируем пустое множество.) Затем переведите цифры в их двоичное представление. Затем замените элементы вашего набора на биты «on».

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

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

(Для доказательства см. бесплатную учебную программу MIT Mathematics for Computer Science, 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/ )

Если вы можете использовать синтаксис SQL - скажем, если вы используете LINQ для доступа к полям структуры или массива или напрямую обращаетесь к базе данных с таблицей «Алфавит» только с одним полем «Письмо», вы может адаптировать следующий код:

SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter

Это вернет все комбинации из 3 букв, несмотря на то, сколько букв у вас в таблице «Алфавит» (это может быть 3, 8, 10, 27 и т. д.). .

Если все, что вы хотите, это все перестановки, а не комбинации (т. е. вы хотите, чтобы «ACB» и «ABC» считались разными, а не отображались только один раз) просто удалите последнюю строку (AND ) и это сделано.

Post-Edit: после повторного чтения вопроса я понимаю, что необходим алгоритм general , а не только определенный для случая выбора 3 Предметы. Ответ Адама Хьюза - полный, к сожалению, я не могу его проголосовать (пока). Этот ответ прост, но работает только тогда, когда вы хотите точно 3 элемента.

Простой рекурсивный алгоритм в Haskell

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

Сначала определим частный случай, т. е. выбрав нулевые элементы. Он производит единственный результат, который представляет собой пустой список (т. Е. Список, содержащий пустой список).

При n> 0, x проходит через каждый элемент списка, а xs - каждый элемент после x.

rest выбирает n - 1 элементы из xs, используя рекурсивный вызов combinations. Конечным результатом функции является список, в котором каждый элемент x : rest (т. Е. Список, который имеет x в качестве главы и rest как хвост) для каждого другого значения x и rest.

> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

И, конечно, поскольку Haskell ленив, список постепенно генерируется по мере необходимости, поэтому вы можете частично оценить экспоненциально большие комбинации.

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
 "abcdefgo","abcdefgp","abcdefgq"]

Вот мое предложение в 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));
    }
}

Array.prototype.combs = function(num) {

    var str = this,
        length = str.length,
        of = Math.pow(2, length) - 1,
        out, combinations = [];

    while(of) {

        out = [];

        for(var i = 0, y; i < length; i++) {

            y = (1 << i);

            if(y & of && (y !== of))
                out.push(str[i]);

        }

        if (out.length >= num) {
           combinations.push(out);
        }

        of--;
    }

    return combinations;
}

В C #:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

Использование:

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

Результат:

123
124
125
134
135
145
234
235
245
345

У меня был алгоритм перестановки, который я использовал для эйлера проекта, в python:

def missing(miss,src):
    "Returns the list of items in src not present in miss"
    return [i for i in src if i not in miss]


def permutation_gen(n,l):
    "Generates all the permutations of n items of the l list"
    for i in l:
        if n<=1: yield [i]
        r = [i]
        for j in permutation_gen(n-1,missing([i],l)):  yield r+j

Если

n<len(l) 

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

Это генератор, поэтому вы используете его примерно так:

for comb in permutation_gen(3,list("ABCDEFGH")):
    print comb 

В C ++ следующая процедура будет производить все комбинации расстояния длины (сначала k) между диапазоном [первым, последним]:

#include <algorithm>

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Его можно использовать следующим образом:

#include <string>
#include <iostream>

int main()
{
    std::string s = "12345";
    std::size_t comb_size = 3;
    do
    {
        std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
    } while (next_combination(s.begin(), s.begin() + comb_size, s.end()));

    return 0;
}

Это напечатает следующее:

123
124
125
134
135
145
234
235
245
345

Допустим, ваш массив букв выглядит так: «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
...

Написанный в коде, это выглядит примерно так

void print_combinations(const char *string)
{
    int i, j, k;
    int len = strlen(string);

    for (i = 0; i < len - 2; i++)
    {
        for (j = i + 1; j < len - 1; j++)
        {
            for (k = j + 1; k < len; k++)
                printf("%c%c%c\n", string[i], string[j], string[k]);
        }
    }
}

https://gist.github.com/3118596

Существует реализация для JavaScript. Он имеет функции для получения k-комбинаций и всех комбинаций массива любых объектов. Примеры:

k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]

combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

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

1. Выводит все K-индексы в хорошем формате для любого N, выбирающего K в файл. K-индексы могут быть заменены более описательными строками или буквами. Этот метод позволяет решить этот тип проблемы довольно тривиально.
2. Преобразует K-индексы в собственный индекс записи в таблице отсортированных биномиальных коэффициентов. Этот метод намного быстрее, чем более старые опубликованные методы, основанные на итерации. Он делает это, используя математическое свойство, присущее Треугольнику Паскаля. В моей статье говорится об этом. Я считаю, что я первый, кто открыл и опубликовал эту технику, но я мог ошибаться.
3. Преобразует индекс в отсортированную таблицу биномиальных коэффициентов в соответствующие K-индексы.
4. Использует Метод Mark Dominus для вычисления биномиального коэффициента, который гораздо реже переполняется и работает с большими числами.
5. Класс написан на .NET C # и предоставляет способ управления объекты, связанные с проблемой (если есть), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое, когда true, создаст общий список для хранения объектов, которые будут управляться. Если это значение ложно, то оно не создаст таблицу. Таблицу не нужно создавать, чтобы выполнить описанные выше методы. Для доступа к таблице предоставляются методы доступа.
6. Существует связанный тестовый класс, который показывает, как использовать класс и его методы.

Чтобы прочитать об этом классе и загрузить код, см. Tablizing The Binomial Coeffieicent .

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

And here comes granddaddy COBOL, the much maligned language.

Let's assume an array of 34 elements of 8 bytes each (purely arbitrary selection.)  The
idea is to enumerate all possible 4-element combinations and load them into an array.

We use 4 indices, one each for each position in the group of 4

The array is processed like this:
    idx1 = 1
    idx2 = 2
    idx3 = 3
    idx4 = 4


We vary idx4 from 4 to the end.  For each idx4 we get a unique combination 

групп из четырех. Когда idx4 подходит к концу массива, мы увеличиваем idx3 на 1 и устанавливаем idx4 на idx3 + 1. Затем мы снова запускаем idx4. Таким образом, мы увеличиваем idx3, idx2 и idx1 до тех пор, пока позиция idx1 не станет меньше 4 от конца массива. Это завершает алгоритм.

1           --- pos.1
2          --- pos 2
3          --- pos 3
4          --- pos 4
5
6
7
etc.

First iterations:

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.


A COBOL example:

01  DATA_ARAY.
    05  FILLER     PIC X(8)    VALUE  "VALUE_01".
    05  FILLER     PIC X(8)    VALUE  "VALUE_02".
  etc.
01  ARAY_DATA    OCCURS 34.
    05  ARAY_ITEM       PIC X(8).

01  OUTPUT_ARAY   OCCURS  50000   PIC X(32).

01   MAX_NUM   PIC 99 COMP VALUE 34.

01  INDEXXES  COMP.
    05  IDX1            PIC 99.
    05  IDX2            PIC 99.
    05  IDX3            PIC 99.
    05  IDX4            PIC 99.
    05  OUT_IDX   PIC 9(9).

01  WHERE_TO_STOP_SEARCH          PIC 99  COMP.

* Stop the search when IDX1 is on the third last array element:

COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3     

MOVE 1 TO IDX1

PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
   COMPUTE IDX2 = IDX1 + 1
   PERFORM UNTIL IDX2 > MAX_NUM
      COMPUTE IDX3 = IDX2 + 1
      PERFORM UNTIL IDX3 > MAX_NUM
         COMPUTE IDX4 = IDX3 + 1
         PERFORM UNTIL IDX4 > MAX_NUM
            ADD 1 TO OUT_IDX
            STRING  ARAY_ITEM(IDX1)
                    ARAY_ITEM(IDX2)
                    ARAY_ITEM(IDX3)
                    ARAY_ITEM(IDX4)
                    INTO OUTPUT_ARAY(OUT_IDX)
            ADD 1 TO IDX4
         END-PERFORM
         ADD 1 TO IDX3
      END-PERFORM
      ADD 1 TO IDX2
   END_PERFORM
   ADD 1 TO IDX1
END-PERFORM.

Следующий рекурсивный алгоритм выбирает все комбинации k-элементов из упорядоченного множества:

• выбирает первый элемент i вашей комбинации
• i ] с каждой из комбинаций элементов k-1, выбранных рекурсивно из набора элементов, большего, чем i.

Итерацию выше для каждого i в наборе.

Очень важно, чтобы остальные элементы были больше, чем i, чтобы избежать повторения. Этот путь [3,5] будет выбран только один раз, поскольку [3] в сочетании с [5] вместо двух (условие исключает [5] + [3]). Без этого условия вы получаете варианты вместо комбинаций.

Другая версия C # с ленивым поколением комбинационных индексов. Эта версия поддерживает единый массив индексов для определения сопоставления между списком всех значений и значениями для текущей комбинации, т. Е. Постоянно использует дополнительное пространство O (k) в течение всего времени выполнения. Код генерирует отдельные комбинации, включая первый, в O (k) времени.

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
    if (k < 0 || values.Length < k)
        yield break; // invalid parameters, no combinations possible

    // generate the initial combination indices
    var combIndices = new int[k];
    for (var i = 0; i < k; i++)
    {
        combIndices[i] = i;
    }

    while (true)
    {
        // return next combination
        var combination = new T[k];
        for (var i = 0; i < k; i++)
        {
            combination[i] = values[combIndices[i]];
        }
        yield return combination;

        // find first index to update
        var indexToUpdate = k - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
        {
            indexToUpdate--;
        }

        if (indexToUpdate < 0)
            yield break; // done

        // update combination indices
        for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
        {
            combIndices[indexToUpdate] = combIndex;
        }
    }
}

Код теста:

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

Выход:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

Я создал для этого решение в 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)

Могу ли я представить рекурсивное решение Python для этой проблемы?

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

Пример использования:

>>> len(list(choose_iter("abcdefgh",3)))
56

Мне нравится его простота.

Здесь у вас есть ленивая оцененная версия этого алгоритма, закодированная в C #:

    static bool nextCombination(int[] num, int n, int k)
    {
        bool finished, changed;

        changed = finished = false;

        if (k > 0)
        {
            for (int i = k - 1; !finished && !changed; i--)
            {
                if (num[i] < (n - 1) - (k - 1) + i)
                {
                    num[i]++;
                    if (i < k - 1)
                    {
                        for (int j = i + 1; j < k; j++)
                        {
                            num[j] = num[j - 1] + 1;
                        }
                    }
                    changed = true;
                }
                finished = (i == 0);
            }
        }

        return changed;
    }

    static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
    {
        T[] elem = elements.ToArray();
        int size = elem.Length;

        if (k <= size)
        {
            int[] numbers = new int[k];
            for (int i = 0; i < k; i++)
            {
                numbers[i] = i;
            }

            do
            {
                yield return numbers.Select(n => elem[n]);
            }
            while (nextCombination(numbers, size, k));
        }
    }

И тестовая часть:

    static void Main(string[] args)
    {
        int k = 3;
        var t = new[] { "dog", "cat", "mouse", "zebra"};

        foreach (IEnumerable<string> i in Combinations(t, k))
        {
            Console.WriteLine(string.Join(",", i));
        }
    }

Надеюсь, это поможет вам!

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

Код можно изменить для обертывания, т. Е. 'Dab' из ввода 'abcd' wk = 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

Краткое решение для 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);