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

Question

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

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

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

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

Answer 1

Вот простой код, который печатает все комбинации C (n, m). Он работает путем инициализации и перемещения набора индексов массива, которые указывают на следующую допустимую комбинацию. Индексы инициализируются так, чтобы указывать на самые низкие индексы m (лексикографически наименьшая комбинация). Затем, начиная с m-го индекса, мы пытаемся продвинуть индексы вперед. если индекс достиг своего предела, мы пробуем предыдущий индекс (вплоть до индекса 1). Если мы сможем продвинуть индекс вперед, мы сбросим все большие индексы.

m=(rand()%n)+1; // m will vary from 1 to n

for (i=0;i<n;i++) a[i]=i+1;

// we want to print all possible C(n,m) combinations of selecting m objects out of n
printf("Printing C(%d,%d) possible combinations ...\n", n,m);

// This is an adhoc algo that keeps m pointers to the next valid combination
for (i=0;i<m;i++) p[i]=i; // the p[.] contain indices to the a vector whose elements constitute next combination

done=false;
while (!done)
{
    // print combination
    for (i=0;i<m;i++) printf("%2d ", a[p[i]]);
    printf("\n");

    // update combination
    // method: start with p[m-1]. try to increment it. if it is already at the end, then try moving p[m-2] ahead.
    // if this is possible, then reset p[m-1] to 1 more than (the new) p[m-2].
    // if p[m-2] can not also be moved, then try p[m-3]. move that ahead. then reset p[m-2] and p[m-1].
    // repeat all the way down to p[0]. if p[0] can not also be moved, then we have generated all combinations.
    j=m-1;
    i=1;
    move_found=false;
    while ((j>=0) && !move_found)
    {
        if (p[j]<(n-i)) 
        {
            move_found=true;
            p[j]++; // point p[j] to next index
            for (k=j+1;k<m;k++)
            {
                p[k]=p[j]+(k-j);
            }
        }
        else
        {
            j--;
            i++;
        }
    }
    if (!move_found) done=true;
}

Answer 2

Макрос Lisp генерирует код для всех значений r (по времени)

(defmacro txaat (some-list taken-at-a-time)
  (let* ((vars (reverse (truncate-list '(a b c d e f g h i j) taken-at-a-time))))
    `(
      ,@(loop for i below taken-at-a-time 
           for j in vars 
           with nested = nil 
           finally (return nested) 
           do
             (setf 
              nested 
              `(loop for ,j from
                    ,(if (< i (1- (length vars)))
                         `(1+ ,(nth (1+ i) vars))
                         0)
                  below (- (length ,some-list) ,i)
                    ,@(if (equal i 0) 
                          `(collect 
                               (list
                                ,@(loop for k from (1- taken-at-a-time) downto 0
                                     append `((nth ,(nth k vars) ,some-list)))))
                          `(append ,nested))))))))

Итак,

CL-USER> (macroexpand-1 '(txaat '(a b c d) 1))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 1)
    COLLECT (LIST (NTH A '(A B C D))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 2))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 2)
      APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 1)
                   COLLECT (LIST (NTH A '(A B C D)) (NTH B '(A B C D)))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 3))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 3)
      APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 2)
                   APPEND (LOOP FOR C FROM (1+ B) TO (- (LENGTH '(A B C D)) 1)
                                COLLECT (LIST (NTH A '(A B C D))
                                              (NTH B '(A B C D))
                                              (NTH C '(A B C D))))))
T

CL-USER> 

И

CL-USER> (txaat '(a b c d) 1)
((A) (B) (C) (D))
CL-USER> (txaat '(a b c d) 2)
((A B) (A C) (A D) (B C) (B D) (C D))
CL-USER> (txaat '(a b c d) 3)
((A B C) (A B D) (A C D) (B C D))
CL-USER> (txaat '(a b c d) 4)
((A B C D))
CL-USER> (txaat '(a b c d) 5)
NIL
CL-USER> (txaat '(a b c d) 0)
NIL
CL-USER> 

Answer 3

#include <stdio.h>

unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
    unsigned int finished = 0;
    unsigned int changed = 0;
    unsigned int i;

    if (k > 0) {
        for (i = k - 1; !finished && !changed; i--) {
            if (ar[i] < (n - 1) - (k - 1) + i) {
                /* Increment this element */
                ar[i]++;
                if (i < k - 1) {
                    /* Turn the elements after it into a linear sequence */
                    unsigned int j;
                    for (j = i + 1; j < k; j++) {
                        ar[j] = ar[j - 1] + 1;
                    }
                }
                changed = 1;
            }
            finished = i == 0;
        }
        if (!changed) {
            /* Reset to first combination */
            for (i = 0; i < k; i++) {
                ar[i] = i;
            }
        }
    }
    return changed;
}

typedef void(*printfn)(const void *, FILE *);

void print_set(const unsigned int *ar, size_t len, const void **elements,
    const char *brackets, printfn print, FILE *fptr)
{
    unsigned int i;
    fputc(brackets[0], fptr);
    for (i = 0; i < len; i++) {
        print(elements[ar[i]], fptr);
        if (i < len - 1) {
            fputs(", ", fptr);
        }
    }
    fputc(brackets[1], fptr);
}

int main(void)
{
    unsigned int numbers[] = { 0, 1, 2 };
    char *elements[] = { "a", "b", "c", "d", "e" };
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    do {
        print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
        putchar('\n');
    } while (next_combination(numbers, n, k));
    getchar();
    return 0;
}

Answer 4

Это рекурсивная программа, которая генерирует комбинации для nCk.Elements в коллекции, предполагаемые от 1 до n

#include<stdio.h>
#include<stdlib.h>

int nCk(int n,int loopno,int ini,int *a,int k)
{
    static int count=0;
    int i;
    loopno--;
    if(loopno<0)
    {
        a[k-1]=ini;
        for(i=0;i<k;i++)
        {
            printf("%d,",a[i]);
        }
        printf("\n");
        count++;
        return 0;
    }
    for(i=ini;i<=n-loopno-1;i++)
    {
        a[k-1-loopno]=i+1;
        nCk(n,loopno,i+1,a,k);
    }
    if(ini==0)
    return count;
    else
    return 0;
}

void main()
{
    int n,k,*a,count;
    printf("Enter the value of n and k\n");
    scanf("%d %d",&n,&k);
    a=(int*)malloc(k*sizeof(int));
    count=nCk(n,k,0,a,k);
    printf("No of combinations=%d\n",count);
}

Answer 5

А вот версия Clojure , в которой используется тот же алгоритм, который я описал в своем ответе на реализацию OCaml :

(defn select
  ([items]
     (select items 0 (inc (count items))))
  ([items n1 n2]
     (reduce concat
             (map #(select % items)
                  (range n1 (inc n2)))))
  ([n items]
     (let [
           lmul (fn [a list-of-lists-of-bs]
                     (map #(cons a %) list-of-lists-of-bs))
           ]
       (if (= n (count items))
         (list items)
         (if (empty? items)
           items
           (concat
            (select n (rest items))
            (lmul (first items) (select (dec n) (rest items))))))))) 

Он предоставляет три способа вызова:

(a) для точно n выбранных пунктов, как того требует вопрос:

  user=> (count (select 3 "abcdefgh"))
  56

(b) от n1 до n2 выбранные позиции:

user=> (select '(1 2 3 4) 2 3)
((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3))

(c) в диапазоне от 0 до размера коллекции выбранных предметов:

user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))

Answer 6

В VB.Net этот алгоритм собирает все комбинации из n чисел из набора чисел (PoolArray). например все комбинации из 5 пиков из "8,10,20,33,41,44,47".

Sub CreateAllCombinationsOfPicksFromPool(ByVal PicksArray() As UInteger, ByVal PicksIndex As UInteger, ByVal PoolArray() As UInteger, ByVal PoolIndex As UInteger)
    If PicksIndex < PicksArray.Length Then
        For i As Integer = PoolIndex To PoolArray.Length - PicksArray.Length + PicksIndex
            PicksArray(PicksIndex) = PoolArray(i)
            CreateAllCombinationsOfPicksFromPool(PicksArray, PicksIndex + 1, PoolArray, i + 1)
        Next
    Else
        ' completed combination. build your collections using PicksArray.
    End If
End Sub

        Dim PoolArray() As UInteger = Array.ConvertAll("8,10,20,33,41,44,47".Split(","), Function(u) UInteger.Parse(u))
        Dim nPicks as UInteger = 5
        Dim Picks(nPicks - 1) As UInteger
        CreateAllCombinationsOfPicksFromPool(Picks, 0, PoolArray, 0)

Answer 7

Поскольку язык программирования не упоминается, я предполагаю, что списки тоже в порядке. Итак, вот версия OCaml, подходящая для коротких списков (без хвостовой рекурсии). При наличии списка l элементов любого типа и целого числа n будет возвращен список всех возможные списки, содержащие n элементов l , если предположить, что порядок элементов в списках результатов игнорируется, т.е. list [ 'a'; 'b'] совпадает с ['b'; 'a'] и будет сообщено один раз. Таким образом, размер результирующего списка будет ((List.length l) Выберите n).

Интуиция рекурсии заключается в следующем: вы берете верхнюю часть списка и затем делаете два рекурсивных вызова:

• рекурсивный вызов 1 (RC1): в конец списка, но выберите n-1 элементов
• рекурсивный вызов 2 (RC2): в конец списка, но выберите n элементов

, чтобы объединить рекурсивные результаты, умножьте список (укажите нечетное имя) на начало списка с результатами RC1, а затем добавьте (@) результаты RC2. Умножение списка - это следующая операция lmul:

a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]

lmul реализовано в приведенном ниже коде как

List.map (fun x -> h::x)

Рекурсия прекращается, когда размер списка равен количеству элементов, которые вы хотите выбрать, и в этом случае вы просто возвращаете сам список.

Итак, вот четыре строки в OCaml, которые реализуют вышеуказанный алгоритм:

    let rec choose l n = match l, (List.length l) with                                 
    | _, lsize  when n==lsize  -> [l]                                
    | h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)   
    | [], _ -> []    

Answer 8

void combine(char a[], int N, int M, int m, int start, char result[]) {
    if (0 == m) {
        for (int i = M - 1; i >= 0; i--)
            std::cout << result[i];
        std::cout << std::endl;
        return;
    }
    for (int i = start; i < (N - m + 1); i++) {
        result[m - 1] = a[i];
        combine(a, N, M, m-1, i+1, result);
    }
}

void combine(char a[], int N, int M) {
    char *result = new char[M];
    combine(a, N, M, M, 0, result);
    delete[] result;
}

В первой функции m обозначает, сколько еще вам нужно выбрать, а start обозначает, с какой позиции в массиве вы должны начать выбирать.

Answer 9

JavaScript, генераторный, рекурсивный подход:

function *nCk(n,k){
  for(var i=n-1;i>=k-1;--i)
    if(k===1)
      yield [i];
    else
      for(var temp of nCk(i,k-1)){
        temp.unshift(i);
        yield temp;
      }
}

function test(){
  try{
    var n=parseInt(ninp.value);
    var k=parseInt(kinp.value);
    log.innerText="";
    var stop=Date.now()+1000;
    if(k>=1)
      for(var res of nCk(n,k))
        if(Date.now()<stop)
          log.innerText+=JSON.stringify(res)+" ";
        else{
          log.innerText+="1 second passed, stopping here.";
          break;
        }
  }catch(ex){}
}

n:<input id="ninp" oninput="test()">
&gt;= k:<input id="kinp" oninput="test()"> &gt;= 1
<div id="log"></div>

Таким образом (уменьшая i и unshift()) он производит комбинации и элементы внутри комбинаций в порядке убывания, что несколько радует глаз.
Тест останавливается через 1 секунду, поэтому ввод странных чисел относительно безопасен.

Answer 10

C-код для алгоритма L (лексикографические комбинации) в разделе 7.2.1.3 Искусство компьютерного программирования, том 4A: комбинаторные алгоритмы, часть 1 :

#include <stdio.h>
#include <stdlib.h>

void visit(int* c, int t) 
{
  // for (int j = 1; j <= t; j++)
  for (int j = t; j > 0; j--)
    printf("%d ", c[j]);
  printf("\n");
}

int* initialize(int n, int t) 
{
  // c[0] not used
  int *c = (int*) malloc((t + 3) * sizeof(int));

  for (int j = 1; j <= t; j++)
    c[j] = j - 1;
  c[t+1] = n;
  c[t+2] = 0;
  return c;
}

void comb(int n, int t) 
{
  int *c = initialize(n, t);
  int j;

  for (;;) {
    visit(c, t);
    j = 1;
    while (c[j]+1 == c[j+1]) {
      c[j] = j - 1;
      ++j;
    }
    if (j > t) 
      return;
    ++c[j];
  }
  free(c);
}

int main(int argc, char *argv[])
{
  comb(5, 3);
  return 0;
}