Перестановка всех возможных (0, 1) массивов значений

Question

Я пишу алгоритм для генерации всех возможных перестановок массива такого типа:

n = длина
k = количество единиц в массиве

Таким образом, это означает, что если у нас есть k 1, у нас будет n-k 0 в массиве.

Например: n = 5; k = 3;

Итак, очевидно, что для этого массива есть 5 возможных 3 перестановок, потому что
n! / (k! (n-k)!
5! / (3! 2!) = (5 * 4) / 2 = 10
возможные значения для массива

Вот все значения:
11100
11010
11001
10110
10101
10011
01110
01101
01011
00111

Полагаю, мне следует использовать рекурсивные алгоритмы, но я просто этого не вижу. Я пишу этот алгоритм на C ++.

Буду признателен за любую помощь!

Answer 1

Просто начните с 00111, а затем используйте std::next_permutation, чтобы сгенерировать остаток:

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::string s = "00111";
    do
    {
        std::cout << s << '\n';
    }
    while (std::next_permutation(s.begin(), s.end()));
}

выход:

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

Answer 2

Вы можете разделить комбинации на комбинации, начинающиеся с 1 (n-1, k-1), и комбинации, начинающиеся с 0 (n-1, k).

По сути, это рекурсивнаяформула для функции выбора .

Answer 3

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

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

Я искал StackOverflow и просто увидел картинки в этот ответ зажег лампочку над моей головой.

Answer 4

Если вы хотите сделать это рекурсивно, обратите внимание, что требуемый набор перестановок равен всем тем, которые начинаются с "1", вместе со всеми, которые начинаются с "0".Таким образом, при расчете (n,k) вы будете рекурсивно использовать (n-1,k-1) и (n-1,k), в особых случаях, когда k = 0 и k = n.

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

Answer 5

Это примерно 0-1 перестановок, так что, вероятно, гораздо эффективнее итеративно увеличивать целое число, и, если у него есть желаемое количество битов, распечатать его двоичное представление.

Вот эскиз:

void printAllBinaryPermutations(int k, int n)  
{  
  int max = pow(2, n) - 1;  
  for(int i=0; i<=max;i++)  
  {  
    if(hasBitCountOf(i, k)) // i has k 1's?  
    {  
      printAsBinary(i, n);  
    }  
  }  
}  


bool hasBitCountOf(int v, int expectedBitCount)  
{  
    int count = 0;  
    while(v>0 && count<= expectedBitCount)  
    {  
        int half = v >> 1;  
        if(half<<1 != v)  
        {  
            // v is odd  
            count++;  
        }  
        v = half;  
    }  

    return count==expectedBitCount;  
}  


void printAsBinary(int number, int strLen)  
{  
  for(int i=strLen-1; i>=0; i--)  
  {  
    bool is0 = (number & pow(2,i)) == 0;  
    if (is0)  
    {  
      cout<<'0';  
    }  
    else  
    {  
      cout<<'1';  
    }  
  }   

  cout<<endl;  

}

Answer 6

Домашнее задание и рекурсивный алгоритм? ОК, пошли:

Базовый корпус: У вас есть два элемента, назовите их «a» и «b» и произведите конкатенации ab, затем ba.

Шаг: Если ваш второй Элемент длиннее 1, разделите его на первое поле / букву и другую часть и передайте это рекурсивно как параметры самой функции.

Это будет работать для любых строк и массивов.

Answer 7

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

permutation (prefix, ones, zeros, cur) {
    if (ones + zeros == 0) output(cur);
    else {
        if (cur != -1) prefix = concat(prefix,cur);
        if (ones > 0) permutation(prefix, ones - 1, zeros, 1);
        if (zeros > 0) permutation(prefix, ones, zeros - 1, 0);
    }        
}

permutation(empty, 3, 2, -1);

Greetz
back2dos