Все возможные комбинации из n предметов, выбранных случайным образом из набора из х предметов (алгоритм)

Question

У меня есть набор из x строковых элементов, например («A», «B», «C», «D», «E», «F») Мне нужно знать формулу, которая рассчитывает, сколько комбинаций из n предметов и какой алгоритм генерирует все возможные комбинации например если нам нужно выбрать 4 элемента из списка случайным образом. эти 4 пункта могут быть: («A», «B», «C», «D») или («А», «В», «С», «Е») или («А», «В», «С», «F») или ("A", "B", "D", "E") ... и т. Д. Мне нужна формула, которая вычисляет, сколько наборов элементов будет сгенерировано без повторения, то есть мы рассматриваем («A», «B», «C», «D») как одну из приведенных комбинаций, которую мы не можем рассматривать одинаковыми элементами в качестве еще одной результирующей комбинации с заменой позиций предметов в наборе, например («A», «B», «D», «C») Также мне нужен алгоритм, который генерирует все возможные комбинации на любом языке программирования. [C #, VB.NET, Java, C ++]

Спасибо за любую помощь.

Answer 1

Выбор p из n предметов, это формула, чтобы сказать вам, сколько комбинаций.

                  n!
n choose p  = -----------
               p! (n-p)!

Google калькулятор сделает все за вас:

http://www.google.com/search?q=6+choose+4

6 выберите 4 = 15

Answer 2

Формула для комбинации , которую вы описываете, приведена в ответе @Mark Harrison. Однако, включите это уравнение, и оно взорвется, потому что математика предназначена для исключения.

Например, 50 выбирают 49 - это то же самое, что выбирать, какой элемент исключать, поэтому есть 50 вариантов. Однако формула потребует от вас вычисления

   50!       3.04140932e64
-------- = ----------------- = 50
1! * 49!   1 * 6.08281864e62

Уравнение, которое вы «действительно» хотите для x выбрать y, равно

x * (x-1) * ... * (x-n+1)
-------------------------
n * (n-1) * ... * 2 * 1

Некоторый простой C-код [обратите внимание, что это оптимизирует C (x, y) = C (x, x-y) - это должно быть легко увидеть из формулы комбинации]:

int c(int x, int y)
{
    int num = 1, denom = 1;
    int i;
    if (y > x-y)
        y = x - y;
    for (i = 0; i < y; ++i)
    {
        num *= (x - i);
        denom *= (y - i);
    }
    return num/denom;
}

Итак, если вам нужны все возможные комбинации букв «ABCDEF», где вы выбираете 4 буквы, то есть c(6,4).

Answer 3

Мне нужен алгоритм, который генерирует все возможные комбинации на любом языке программирования.

Хорошо, вот решение на одной строке в Haskell:

import Data.List (subsequences)

n `outOf` xs = filter ((n ==) . length) (subsequences xs)

test = 4 `outOf` ["A", "B", "C", "D", "E", "F"]

*Main> test
[["A","B","C","D"],["A","B","C","E"],["A","B","D","E"],["A","C","D","E"],["B","C
","D","E"],["A","B","C","F"],["A","B","D","F"],["A","C","D","F"],["B","C","D","F
"],["A","B","E","F"],["A","C","E","F"],["B","C","E","F"],["A","D","E","F"],["B",
"D","E","F"],["C","D","E","F"]]
*Main> length test
15

Answer 4

Вам нужна Биноминальная теорема , и вам нужны вложенные циклы. Что касается реализации на одном из ваших языков программирования, не так уж сложно написать. Если вы посмотрите вокруг, вы обнаружите, что этот вопрос регулярно задается на SO, и вы найдете людей, голосующих за закрытие вашего вопроса по этой причине.

Answer 5

Да, треугольник Паскаля работает.

int dp[MAX_X][MAX_Y] = {0};

dp[0][0] = 1;
for (int i = 1; i <= X; i++) {
    dp[i][0] = dp[i][i] = 0;
    for (int j = 1; j < min(i, Y + 1); j++)
        dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
}

print(dp[X][Y])

В качестве альтернативы, вы можете сделать что-нибудь, используя трюк со скользящим окном.

Опять же, я думаю, что формула работает лучше, если только значения не станут слишком большими.

Answer 6

Вы можете вычислить количество комбинаций, используя Треугольник Паскаля . Чтобы найти реальные комбинации, вы можете использовать обычную рекурсию.

Answer 7

Вы также можете перейти на Лексикографический заказ .

Примерно так:

#include <stdio.h>

void print(const int *v, const int size)
{
    int i;
    if (v != 0) {
        for (i = 0; i < size; i++) {
            printf("%4d", v[i] );
        }
        printf("\n");
    }
} // print


void visit(int *Value, int N, int k)
{
    int i;
    static level = -1;
    level = level+1; Value[k] = level;

    if (level == N)
        print(Value, N);
    else
        for (i = 0; i < N; i++)
            if (Value[i] == 0)
                visit(Value, N, i);

    level = level-1; Value[k] = 0;
}


main()
{
    const int N = 4;
    int Value[N];
    int i;
    for (i = 0; i < N; i++) {
        Value[i] = 0;
    }
    visit(Value, N, 0);
}