迭代查找字符数组大小为 k 的所有组合（N 选择 K）

Question

我目前正在将这个问题作为个人项目来处理。

基本上：

给定一个元素数组，例如E = {1,2,a,b} 和
给定一个数字 K，例如K = 2
我想要 return 所有 Combinations 个尺寸为 K 的 E（E 选择 K）
例如{{1,1}, {1,2}, {1,a}, {1,b}, {2,1}, ... , {b,1}, {b,2}, {b, a}, {b,b}}

我已经使用以下函数递归地实现了这一点：

char[] pool = new char[]{'1', '2', '3'};

public void buildStringRec(char[] root, int pos, int length){
    for(char c : pool){
        char[] newRoot = root.clone();
        newRoot[pos] = c;
        if(pos+1 < length){
            buildStringRec(newRoot, pos+1, length);
        } else{
            System.out.println(String.valueOf(root));
        }
    }
}

其中 pool 是 E，length 是 K。

所以我们会调用：buildStringRec(new char[2], 0, 2); 并得到

这可以迭代完成吗？我一直在努力思考如何使用可变长度来做到这一点。

如有任何帮助，我们将不胜感激！如果需要，我可以按原样 post 我的代码，但由于我的重试，它更改得如此频繁，以至于我 post 它几乎没用了。

此外，我不想使用 Apache 或 String Builder 来执行此操作，因为我想了解如何执行此操作的概念。我不是简单地要求代码。伪代码只要解释清楚就好了。

谢谢！

编辑

我正在使用这个网站来测试所有呈现给我的选项：https://ideone.com/k1WIa6
随意分叉并尝试一下！

Answer 1

递归求解

对我来说，递归解决方案似乎是最好的选择。
您可以用堆栈替换克隆路径数组以提高性能：

char[] pool = new char[]{'1', '2', '3'};
Stack<int> stack = new Stack<int>();

// Actually, resulting length should be the same length as pool array
int length = pool.length;

public void buildStringRec(int pos)
{
    if (length == pos + 1) 
    {
        System.out.println(String.valueOf(root));
        return;
    }

    for(char c : pool){
        stack.Push(c);
        buildStringRec(pos + 1);
        stack.Pop(c);
    }
}

迭代解决方案

假设出于某种原因，您需要反复执行此操作。
我相信有更好的解决方案。但是，这是我能做到的最好的了。

您可以将您的任务改写为另一个任务：

How to output ALL numbers in base N of length N.

假设您有一个长度为 3 的数组：{'a', 1, 'z'}.
您想要的答案是：

a-a-a    a-a-1    a-a-z
a-1-a    a-1-1    a-1-z
a-z-a    a-z-1    a-z-z
1-a-a    1-a-1    1-a-z

现在，让我们看看这些值的索引：

0-0-0    0-0-1    0-0-2
0-1-0    0-1-1    0-1-2
0-2-0    0-2-1    0-2-2 
2-0-0    2-0-1    2-0-2

实际上，这是一个以 3 为底的连续数字：000, 001, 002, 010, 011, 012, 020, 021, 022, 200, 201, 202。

记住他们的计数公式：base ^ length。在我们的例子中，length == base。因此，它是 base ^ base.

现在，我们的任务变得更容易了：

int[] toBase(long bs, long value)
{ 
    int[] result = new int[bs];
    for (long i = bs - 1; i >= 0; i--)
    {
        result[i] = (int)(value % bs);
        value = value / bs;
    }
    return result;
}

long Pow(long a, long b)
{
    long result = 1;
    for (int i = 0; i < b; i++) result *= a;
    return result;
}

char[] pool = new char[] {'a', 'b', 'c'};

void outputAll()
{
    long n = pool.Length;
    for (long i = 0; i < Pow(n, n); i++)
    {
        int[] indices = toBase(n, i);
        for (int j = 0; j < n; j++)
            Console.Write("{0} ", pool[indices[j]]);
        Console.WriteLine();
    }
}

当然，可以有一些优化：

不用每次都计算toBase。从 000 开始并每次计算下一个数字更容易和更高效。
您可以更改 Pow 函数以使用快速 exponentiation by squaring 算法等

这只是为了解释一种方法而提供的示例。

请记住，长度为 3 的数组只有 27 种这样的组合。但是，长度为 7 的数组将有 823543。它呈指数增长。

工作样本

这里是DotNetFiddle working Demo.

只需更改 pool 数组值即可获得结果。在这里和上面的所有示例中，我都使用了 C#。它可以很容易地转换为 C++ :)

对于我来说，它适用于长达 7 的长度（大约 1 - 1.5 秒）。
当然，您需要删除控制台输出才能获得这样的结果。控制台输出工作真的很慢。

Answer 2

这是另一个迭代解决方案：

您可以创建一个大小为 K 的整数数组作为计数器来记录您完成组合的进度，并创建一个字符数组来存储当前组合。

打印每一个后，通过增加一个计数器值继续下一个组合，如果它 "overflows" 达到等于 E 中元素数的值，则将其重置为零并通过在下一个位置递增计数器来执行进位，检查那里是否有溢出等等。有点像汽车中的里程表，只是数字与 E 中的值相关联。一旦最后一个位置溢出，那么您就生成了所有可能的组合。

我已经从数组中的最后一个值开始递增计数器并向下移动以获得与示例中相同的输出，但这当然不是必需的。该算法不检查重复项。

您不必存储当前组合的字符数组，您可以每次在基于计数器的 for 循环中重新生成它，但这可能效率较低。此方法仅更新更改的值。

public static void buildStrings(char[] root, int length)
{
    // allocate an int array to hold the counts:
    int[] pos = new int[length];
    // allocate a char array to hold the current combination:
    char[] combo = new char[length];
    // initialize to the first value:
    for(int i = 0; i < length; i++)
        combo[i] = root[0];

    while(true)
    {
        // output the current combination:
        System.out.println(String.valueOf(combo));

        // move on to the next combination:
        int place = length - 1;
        while(place >= 0)
        {
            if(++pos[place] == root.length)
            {
                // overflow, reset to zero
                pos[place] = 0;
                combo[place] = root[0];
                place--; // and carry across to the next value
            }
            else
            {
                // no overflow, just set the char value and we're done
                combo[place] = root[pos[place]];
                break;
            }
        }
        if(place < 0)
            break;  // overflowed the last position, no more combinations
    }
}

ideone.com demo

Answer 3

一个简单的迭代解决方案是

创建一个数组来为每个字符保存所需输出长度的索引
然后遍历索引并打印索引对应的池中的每个字符
然后递增索引数组的最后一个索引
如果最后一个索引等于池长度
- 将其设为零
- 增加上一个索引
- 重复前面的索引，直到到达数组的开头或索引不等于池长度

下面是Java

中的一些示例代码

char[] pool = new char[]{'1', '2', '3'};

public void buildStrings(int length){

  int[] indexes = new int[length];
  // In Java all values in new array are set to zero by default
  // in other languages you may have to loop through and set them.

  int pMax = pool.length;  // stored to speed calculation
  while (indexes[0] < pMax){ //if the first index is bigger then pMax we are done

    // print the current permutation
    for (int i = 0; i < length; i++){
      System.out.print(pool[indexes[i]]);//print each character
    }
    System.out.println(); //print end of line

    // increment indexes
    indexes[length-1]++; // increment the last index
    for (int i = length-1; indexes[i] == pMax && i > 0; i--){ // if increment overflows 
      indexes[i-1]++;  // increment previous index
      indexes[i]=0;   // set current index to zero  
    }     
  }
}

Answer 4

迭代求解

这是我在 C/C++ 中开发的算法，具有迭代函数和恒定的空间复杂度

它处理 C 数组的索引，因此它可以用于任何类型的数据，这里是一个字符数组（C++ 字符串），它可以是一串数字

函数1：生成所有可能的组合

// str: string of characters or digits
void GenerateAll(string str, int k)
{
    int n = str.length();

    // initialization of the first subset containing k elements
    int *sub_tab = new int[k];
    for(int j(0); j<k; ++j)
    {
        sub_tab[j] = j;
    }

    do
    {   
        // Convert combination to string
        char *sub_str = new char[k];
        for(int j(0); j<k; ++j)
        {
            sub_str[j] = str[sub_tab[j]];
        }
        // Print combinations of each set
        Combinations(sub_str);
        // get next sub string
    } while (AddOne(sub_tab, k-1, n) == true);

    delete [] sub_tab;      
}

函数 2：为每个集合生成所有组合

void Combinations(string str)
{
    int n = str.length();

    // Compute all factorials from 0 to n
    unsigned long int * factorials = new unsigned long int[n+1];
    factorials[0] = 1;
    for(int i = 1; i<=n; ++i)
        factorials[i] = factorials[i-1] * i;

    char *tab = new char[n];

    // Initialization with the first combination 0123...n-1
    for(int i(0); i<n; ++i)
    {
        tab[i] = i;
        cout << str[i] << " ";
    }
    cout << endl;

    for(unsigned long int i(1); i < factorials[n]; ++i)
    {
        for (int j(0); j < n; ++j)
        {
            if(i % factorials[n-j-1] == 0)
            {
                // increment tab[j] (or find the next available)
                SetNextAvailable(tab, j, n);
            }
        }
        for (int j(0); j < n; ++j)
        {
            cout << str[tab[j]] << " "; 
        }
        cout << endl;
    }

    delete [] factorials;
}

函数 SetNextAvailable()

void SetNextAvailable(char *tab, int j, int n)
{
    bool finished;
    do
    {
        finished = true;
        ++(*(tab+j));
        if (*(tab+j) == n) *(tab+j) = 0;
        for (int i(0); i < j; ++i)
        {
            if ( *(tab+i) == *(tab+j) )
            {
                finished = false;
                break;
            }
        }
    } while(finished == false);
}

函数 AddOne()

bool AddOne(int *tab, int k, int n)
{
    int i;
    for(i=k; i>=0; --i)
    {
        if(((++tab[i]) + (k-i)) != n)
            break;
    }
    if(i == -1)
        return false;
    else
    {
        for(int j=i+1; j<=k; ++j)
        {
            tab[j] = tab[j-1] + 1;
        }
        return true;
    }
}

迭代查找字符数组大小为 k 的所有组合（N 选择 K）

Iteratively find all combinations of size k of an array of characters (N choose K)

algorithm

iteration

combinations

permutation

variable-length

编辑

递归求解

迭代解决方案

工作样本