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

Question

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

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

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

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

Answer 1

В Python похож на Андреа Амбу, но не жестко запрограммирован на выбор трех.

def combinations(list, k):
    """Choose combinations of list, choosing k elements(no repeats)"""
    if len(list) < k:
        return []
    else:
        seq = [i for i in range(k)]
        while seq:
            print [list[index] for index in seq]
            seq = get_next_combination(len(list), k, seq)

def get_next_combination(num_elements, k, seq):
        index_to_move = find_index_to_move(num_elements, seq)
        if index_to_move == None:
            return None
        else:
            seq[index_to_move] += 1

            #for every element past this sequence, move it down
            for i, elem in enumerate(seq[(index_to_move+1):]):
                seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1

            return seq

def find_index_to_move(num_elements, seq):
        """Tells which index should be moved"""
        for rev_index, elem in enumerate(reversed(seq)):
            if elem < (num_elements - rev_index - 1):
                return len(seq) - rev_index - 1
        return None   

Answer 2

Вот простое решение JS:

function getAllCombinations(n, k, f1) {
	indexes = Array(k);
  for (let i =0; i< k; i++) {
  	indexes[i] = i;
  }
  var total = 1;
  f1(indexes);
  while (indexes[0] !== n-k) {
  	total++;
		getNext(n, indexes);
    f1(indexes);
  }
  return {total};
}

function getNext(n, vec) {
	const k = vec.length;
  vec[k-1]++;
	for (var i=0; i<k; i++) {
  	var currentIndex = k-i-1;
    if (vec[currentIndex] === n - i) {
	  	var nextIndex = k-i-2;
      vec[nextIndex]++;
      vec[currentIndex] = vec[nextIndex] + 1;
    }
  }

	for (var i=1; i<k; i++) {
    if (vec[i] === n - (k-i - 1)) {
      vec[i] = vec[i-1] + 1;
    }
  }
	return vec;
} 



let start = new Date();
let result = getAllCombinations(10, 3, indexes => console.log(indexes)); 
let runTime = new Date() - start; 

console.log({
result, runTime
});

Answer 3

Если вы пользователь C ++, вы можете воспользоваться функцией next_permutation:

string name = "abcdefg";
int desiredCharsNumber = 3;
string chosenChars = string(name.size()-desiredCharsNumber,'0') + string(desiredCharsNumber, '1');
do {
    for (int i = 0; i < name.size(); ++i)
        if (chosenChars[i] == '1')
            cout << name[i];
    cout << endl;
} while (next_permutation(chosenChars.begin(), chosenChars.end()));

Answer 4

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

import Data.Semigroup
import Data.Monoid

data Comb = MkComb {count :: Int, combinations :: [[Int]]} deriving (Show, Eq, Ord)

instance Semigroup Comb where
    (MkComb c1 cs1) <> (MkComb c2 cs2) = MkComb (c1 + c2) (cs1 ++ cs2)

instance Monoid Comb where
    mempty = MkComb 0 []

addElem :: Comb -> Int -> Comb
addElem (MkComb c cs) x = MkComb c (map (x :) cs)

comb :: Int -> Int -> Comb
comb n k | n < 0 || k < 0 = error "error in `comb n k`, n and k should be natural number"
comb n k | k == 0 || k == n = MkComb 1 [(take k [k-1,k-2..0])]
comb n k | n < k = mempty
comb n k = comb (n-1) k <> (comb (n-1) (k-1) `addElem` (n-1))

Работает как:

*Main> comb 0 1
MkComb {count = 0, combinations = []}

*Main> comb 0 0
MkComb {count = 1, combinations = [[]]}

*Main> comb 1 1
MkComb {count = 1, combinations = [[0]]}

*Main> comb 4 2
MkComb {count = 6, combinations = [[1,0],[2,0],[2,1],[3,0],[3,1],[3,2]]}

*Main> count (comb 10 5)
252

Answer 5

Очень быстрые комбинации для MetaTrader MQL4, реализованные как объект итератора.

Код так прост для понимания.

Я протестировал множество алгоритмов, этот действительно очень быстрый - примерно в 3 раза быстрее, чем большинство функций next_combination ().

class CombinationsIterator
{
private:
	int input_array[];  // 1 2 3 4 5
	int index_array[];  // i j k
	int m_elements;     // N
	int m_indices;      // K

public:
	CombinationsIterator(int &src_data[], int k)
	{
		m_indices = k;
		m_elements = ArraySize(src_data);
		ArrayCopy(input_array, src_data);
		ArrayResize(index_array, m_indices);

		// create initial combination (0..k-1)
		for (int i = 0; i < m_indices; i++)
		{
			index_array[i] = i;
		}
	}

	// https://stackoverflow.com/questions/5076695
	// bool next_combination(int &item[], int k, int N)
	bool advance()
	{
		int N = m_elements;
		for (int i = m_indices - 1; i >= 0; --i)
		{
			if (index_array[i] < --N)
			{
				++index_array[i];
				for (int j = i + 1; j < m_indices; ++j)
				{
					index_array[j] = index_array[j - 1] + 1;
				}
				return true;
			}
		}
		return false;
	}

	void getItems(int &items[])
	{
		// fill items[] from input array
		for (int i = 0; i < m_indices; i++)
		{
			items[i] = input_array[index_array[i]];
		}
	}
};

Программа драйвера для проверки вышеуказанного класса итератора:

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above class

#define N 5
#define K 3

void OnStart()
{
	int myset[N] = {1, 2, 3, 4, 5};
	int items[K];

	CombinationsIterator comboIt(myset, K);

	do
	{
		comboIt.getItems(items);

		printf("%s", ArrayToString(items));

	} while (comboIt.advance());

}

Output:
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

Answer 6

Как насчет этого ответа ... он печатает все комбинации длины 3 ... и может быть обобщен для любой длины ... Рабочий код ...

#include<iostream>
#include<string>
using namespace std;

void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l  == 3 ){
 cout<<dest<<endl;}
else{
  if(!a.empty() && dest.length() < 3 ){
     combination(a.substr(1,a.length()),dest+a[0]);}
  if(!a.empty() && dest.length() <= 3 ){
      combination(a.substr(1,a.length()),dest);}
 }

 }

 int main(){
 string demo("abcd");
 combination(demo,"");
 return 0;
 }

Answer 7

Вот подход Lisp с использованием макроса. Это работает в Common Lisp и должно работать на других диалектах Lisp.

Приведенный ниже код создает n вложенных циклов и выполняет произвольный фрагмент кода (хранится в переменной body) для каждой комбинации из n элементов из списка lst. Переменная var указывает на список, содержащий переменные, используемые для циклов.

(defmacro do-combinations ((var lst num) &body body)
  (loop with syms = (loop repeat num collect (gensym))
        for i on syms
        for k = `(loop for ,(car i) on (cdr ,(cadr i))
                         do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
                then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
        finally (return k)))

Посмотрим ...

(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))

(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
 (LOOP FOR #:G3216 ON (CDR #:G3217) DO
  (LOOP FOR #:G3215 ON (CDR #:G3216) DO
   (LOOP FOR #:G3214 ON (CDR #:G3215) DO
    (LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
     (PROGN (PPRINT (MAPCAR #'CAR P))))))))

(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))

(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...

Поскольку комбинации не сохраняются по умолчанию, хранилище сводится к минимуму. Возможность выбора кода body вместо сохранения всех результатов также обеспечивает большую гибкость.

Answer 8

Рекурсивно, очень простой ответ, combo, в Free Pascal.

    procedure combinata (n, k :integer; producer :oneintproc);

        procedure combo (ndx, nbr, len, lnd :integer);
        begin
            for nbr := nbr to len do begin
                productarray[ndx] := nbr;
                if len < lnd then
                    combo(ndx+1,nbr+1,len+1,lnd)
                else
                    producer(k);
            end;
        end;

    begin
        combo (0, 0, n-k, n-1);
    end;

«Производитель» располагает массивом продукции, изготовленным для каждой комбинации.

Answer 9

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

stack = [] 
def choose(n,x):
   r(0,0,n+1,x)

def r(p, c, n,x):
   if x-c == 0:
      print stack
      return

   for i in range(p, n-(x-1)+c):
      stack.append(i)
      r(i+1,c+1,n,x)
      stack.pop()

4 выберите 3 или я хочу, чтобы все 3 комбинации чисел начинались с 0 до 4

choose(4,3) 

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

Answer 10

Вот реализация coffeescript

combinations: (list, n) ->
        permuations = Math.pow(2, list.length) - 1
        out = []
        combinations = []

        while permuations
            out = []

            for i in [0..list.length]
                y = ( 1 << i )
                if( y & permuations and (y isnt permuations))
                    out.push(list[i])

            if out.length <= n and out.length > 0
                combinations.push(out)

            permuations--

        return combinations