logo标签列表

迭代地查找字符数组中大小为k的所有组合（从N个元素中选择K个）

algorithmiterationcombinationspermutationvariable-length
9

我目前正在将此问题作为个人项目进行解决。

基本上：

  • 给定一个元素数组，例如 E = {1,2,a,b} 和
  • 给定一个数字 K，例如 K = 2
  • 我想返回所有大小为 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); 并得到

11
12
13
21
22
23
31
32
33

这个可以迭代完成吗？我一直在思考如何处理不同长度的变量。

任何帮助都将不胜感激！如果需要，我可以发布我的代码，但由于我反复尝试而经常更改，因此几乎没有用处。

另外，我不想使用Apache或StringBuilder来完成此操作，因为我想了解如何实现。我不只是要求代码。伪代码也可以，只要清楚地解释。

谢谢！

编辑

我正在使用此网站测试向我提供的所有选项：https://ideone.com/k1WIa6
请随意分叉并尝试它！

严格来说，{1,1} 不是 {1,2,3} 的子集（或者更确切地说，它与 {1} 是同一组，因为集合不能包含相同的元素多次 - 那些将是多重集）。因此，如果您实际上想返回“大小为 K 的 E 的子集的集合”，则 {1,1} 不应该是输出的一部分。然而，您似乎对结果感到满意（这是打印出 E x E 的所有元素），所以我猜这只是术语问题。 - H W
是的，我混淆了术语，这是我的错。我会尽力编辑以使我的意图更加清晰明确。 - zeeveener
@HW这也不算组合，因为可能的组合中不包括{1,1}...也许这更像是“递归交叉乘法”？那么对于长度为3，我应该使用((ExE)xE)来获得我的值？你觉得呢？ - zeeveener
1
是的，“递归交叉乘法”也称为笛卡尔积（或笛卡尔幂）- 参见https://en.wikipedia.org/wiki/Cartesian_product - 可以写作E^K（或对于K = 2，写作ExE）。 - H W
5个回答
4

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

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

以下是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  
    }     
  }
}
这是不正确的，它包括了具有重复索引的组合。 - Eric
4

递归解法

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

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);
    }
}

迭代解决方案

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

您可以将您的任务重新表述为另一个任务：

如何输出长度为N的基数为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

实际上，这是一个三进制下的连续数字：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函数更改为使用快速的平方乘法取幂算法等。

这只是提供一个解决方法的示例。

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

工作样例

这里有一个DotNetFiddle工作演示。

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

至于我，它对长度最长为7的情况运行良好（大约需要1-1.5秒）。
当然，您需要删除控制台输出才能获得这样的结果。控制台输出非常慢。

你使用栈的递归似乎很好。然而，它并不总是比我之前使用的char[]方法更好。你可以使用以下链接查看我的意思。只需将minLength和maxLength更改为不同的值，以获得底部不同的运行时间。 https://ideone.com/k1WIa6 我不明白如何使用你的Base-n方法来解决我正在尝试解决的问题。 - zeeveener
3
这里是另一种迭代的解决方案：
你可以创建一个大小为K的整数数组，用作计数器记录组合的进度，并创建一个字符数组来存储当前组合。
在打印每个组合后，通过增加计数器值之一来进入下一个组合，如果它“溢出”并达到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演示

0

迭代解决方案

这是我在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;
}

设置下一个可用函数()

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;
    }
}
抱歉，当我试图编辑自己的答案时，我错误地编辑了错误的答案，然后我已经回滚了它 :) - Eric
0
这是一个通过迭代实现组合的 go 实现，按照输入顺序排列 （适用于组合和每个组合中的项）。

代码 (go)

package combination_util

import (
    "fmt"
    "golang.org/x/exp/constraints"
)

// count combinations, via iteration, apply given handler on each combination,
func CombInOrderCountViaIter[T constraints.Ordered](is []T, m int, h HandlerCount[T]) int {
    n := len(is)
    if m < 0 || n < m { // invalid
        return 0
    }
    seq := 0
    if m == 0 { // corner: empty,
        h(is, nil, &seq)
        return 1
    }

    indices := make([]int, m)
    for i := 0; i < m; i++ {
        indices[i] = i
    }

    li := m - 1 // last index to move,
    maxIdx := n - 1
    h(is, indices, &seq)
    endIdxForFirst := n - m

    if n > m {
    outer:
        for {
            if indices[li] < maxIdx {
                indices[li]++
                h(is, indices, &seq)
            } else if m > 1 {
                curIdx, preIdx := li, li-1
                for {
                    indices[preIdx]++

                    if indices[curIdx]-indices[preIdx] == 1 {
                        h(is, indices, &seq)
                        if preIdx == 0 && indices[0] == endIdxForFirst { // done
                            break outer
                        }
                    } else {
                        for i, delta := curIdx, 1; i < m; i, delta = i+1, delta+1 {
                            indices[i] = indices[preIdx] + delta
                        }
                        h(is, indices, &seq)
                        break
                    }

                    curIdx--
                    preIdx--
                }
            } else {
                break
            }
        }
    }

    return seq
}

// items are int sequence start from 0, e.g index,
func CombInOrderCountViaIterAsIndex(n, m int, h HandlerCount[int]) int {
    is := GenInputAsIndex(n)
    return CombInOrderCountViaIter(is, m, h)
}

// count & print,
func CombInOrderCountAndPrintViaIterAsIndex(n, m int) int {
    PrintInputAsIndex(n, m, true)
    return CombInOrderCountViaIterAsIndex(n, m, HandlerCountImplPrint[int])
}

// count & print pattern,
func CombInOrderCountAndPrintPatternViaIterAsIndex(n, m int) int {
    PrintInputAsIndex(n, m, true)
    return CombInOrderCountViaIterAsIndex(n, m, HandlerCountImplPrintPattern[int])
}


// extract combination from indices & original input,
func indicesToComb[T constraints.Ordered](is []T, flags []int) []T {
    m := len(flags)
    comb := make([]T, m)
    for i := 0; i < m; i++ {
        comb[i] = is[flags[i]]
    }
    return comb
}

// print input & m,
func PrintInput[T constraints.Ordered](is []T, m int, prependNewLine bool) {
    prefix := ""
    if prependNewLine {
        prefix = "\n"
    }
    fmt.Printf("%s%v, m = %d:\n", prefix, is, m)
}

// print input & m, as indices,
func PrintInputAsIndex(n, m int, prependNewLine bool) {
    is := GenInputAsIndex(n)
    PrintInput[int](is, m, prependNewLine)
}

// generate input of size n, as indices start from 0,
func GenInputAsIndex(n int) []int {
    is := make([]int, n)
    for i := 0; i < n; i++ {
        is[i] = i
    }
    return is
}


const (
    BlackSquare = '◼'
    WhiteSquare = '◻'
)

/* handler types */
type HandlerCount[T constraints.Ordered]   func(is []T, indices []int, seq *int)

/* handler impl */
// count handler - print,
func HandlerCountImplPrint[T constraints.Ordered](is []T, indices []int, seq *int) {
    comb := indicesToComb(is, indices)
    fmt.Printf("\t(%d)\t%v\n", *seq, comb)
    *seq++
}

// count handler - print pattern (white & black square),
func HandlerCountImplPrintPattern[T constraints.Ordered](is []T, indices []int, seq *int) {
    n := len(is)
    pattern := make([]rune, n)

    for i := 0; i < n; i++ {
        pattern[i] = WhiteSquare
    }
    for _, index := range indices {
        pattern[index] = BlackSquare
    }

    fmt.Printf("\t%s\t(%d)\n", string(pattern), *seq)
    *seq++
}

测试

func main() {
    CombInOrderCountAndPrintViaIterAsIndex(5, 3)
    CombInOrderCountAndPrintPatternViaIterAsIndex(10, 5)
}

输出

  • print combination, via CombInOrderCountAndPrintViaIterAsIndex()
    n = 5, m = 3, generated input = [0 1 2 3 4]:

      (0) [0 1 2]
  (1) [0 1 3]
  (2) [0 1 4]
  (3) [0 2 3]
  (4) [0 2 4]
  (5) [0 3 4]
  (6) [1 2 3]
  (7) [1 2 4]
  (8) [1 3 4]
  (9) [2 3 4]

  • print pattern, via CombInOrderCountAndPrintPatternViaIterAsIndex()
    n = 10, m = 5, generated input = [0 1 2 3 4 5 6 7 8 9]:

      ◼◼◼◼◼◻◻◻◻◻  (0)
  ◼◼◼◼◻◼◻◻◻◻  (1)
  ◼◼◼◼◻◻◼◻◻◻  (2)
  ◼◼◼◼◻◻◻◼◻◻  (3)
  ◼◼◼◼◻◻◻◻◼◻  (4)
  ◼◼◼◼◻◻◻◻◻◼  (5)
  ◼◼◼◻◼◼◻◻◻◻  (6)
  ◼◼◼◻◼◻◼◻◻◻  (7)
  ◼◼◼◻◼◻◻◼◻◻  (8)
  ◼◼◼◻◼◻◻◻◼◻  (9)
  ◼◼◼◻◼◻◻◻◻◼  (10)
  ◼◼◼◻◻◼◼◻◻◻  (11)
  ◼◼◼◻◻◼◻◼◻◻  (12)
  ◼◼◼◻◻◼◻◻◼◻  (13)
  ◼◼◼◻◻◼◻◻◻◼  (14)
  ◼◼◼◻◻◻◼◼◻◻  (15)
  ◼◼◼◻◻◻◼◻◼◻  (16)
  ◼◼◼◻◻◻◼◻◻◼  (17)
  ◼◼◼◻◻◻◻◼◼◻  (18)
  ◼◼◼◻◻◻◻◼◻◼  (19)
  ◼◼◼◻◻◻◻◻◼◼  (20)
  ◼◼◻◼◼◼◻◻◻◻  (21)
  ◼◼◻◼◼◻◼◻◻◻  (22)
  ◼◼◻◼◼◻◻◼◻◻  (23)
  ◼◼◻◼◼◻◻◻◼◻  (24)
  ◼◼◻◼◼◻◻◻◻◼  (25)
  ◼◼◻◼◻◼◼◻◻◻  (26)
  ◼◼◻◼◻◼◻◼◻◻  (27)
  ◼◼◻◼◻◼◻◻◼◻  (28)
  ◼◼◻◼◻◼◻◻◻◼  (29)
  ◼◼◻◼◻◻◼◼◻◻  (30)
  ◼◼◻◼◻◻◼◻◼◻  (31)
  ◼◼◻◼◻◻◼◻◻◼  (32)
  ◼◼◻◼◻◻◻◼◼◻  (33)
  ◼◼◻◼◻◻◻◼◻◼  (34)
  ◼◼◻◼◻◻◻◻◼◼  (35)
  ◼◼◻◻◼◼◼◻◻◻  (36)
  ◼◼◻◻◼◼◻◼◻◻  (37)
  ◼◼◻◻◼◼◻◻◼◻  (38)
  ◼◼◻◻◼◼◻◻◻◼  (39)
  ◼◼◻◻◼◻◼◼◻◻  (40)
  ◼◼◻◻◼◻◼◻◼◻  (41)
  ◼◼◻◻◼◻◼◻◻◼  (42)
  ◼◼◻◻◼◻◻◼◼◻  (43)
  ◼◼◻◻◼◻◻◼◻◼  (44)
  ◼◼◻◻◼◻◻◻◼◼  (45)
  ◼◼◻◻◻◼◼◼◻◻  (46)
  ◼◼◻◻◻◼◼◻◼◻  (47)
  ◼◼◻◻◻◼◼◻◻◼  (48)
  ◼◼◻◻◻◼◻◼◼◻  (49)
  ◼◼◻◻◻◼◻◼◻◼  (50)
  ◼◼◻◻◻◼◻◻◼◼  (51)
  ◼◼◻◻◻◻◼◼◼◻  (52)
  ◼◼◻◻◻◻◼◼◻◼  (53)
  ◼◼◻◻◻◻◼◻◼◼  (54)
  ◼◼◻◻◻◻◻◼◼◼  (55)
  ◼◻◼◼◼◼◻◻◻◻  (56)
  ◼◻◼◼◼◻◼◻◻◻  (57)
  ◼◻◼◼◼◻◻◼◻◻  (58)
  ◼◻◼◼◼◻◻◻◼◻  (59)
  ◼◻◼◼◼◻◻◻◻◼  (60)
  ◼◻◼◼◻◼◼◻◻◻  (61)
  ◼◻◼◼◻◼◻◼◻◻  (62)
  ◼◻◼◼◻◼◻◻◼◻  (63)
  ◼◻◼◼◻◼◻◻◻◼  (64)
  ◼◻◼◼◻◻◼◼◻◻  (65)
  ◼◻◼◼◻◻◼◻◼◻  (66)
  ◼◻◼◼◻◻◼◻◻◼  (67)
  ◼◻◼◼◻◻◻◼◼◻  (68)
  ◼◻◼◼◻◻◻◼◻◼  (69)
  ◼◻◼◼◻◻◻◻◼◼  (70)
  ◼◻◼◻◼◼◼◻◻◻  (71)
  ◼◻◼◻◼◼◻◼◻◻  (72)
  ◼◻◼◻◼◼◻◻◼◻  (73)
  ◼◻◼◻◼◼◻◻◻◼  (74)
  ◼◻◼◻◼◻◼◼◻◻  (75)
  ◼◻◼◻◼◻◼◻◼◻  (76)
  ◼◻◼◻◼◻◼◻◻◼  (77)
  ◼◻◼◻◼◻◻◼◼◻  (78)
  ◼◻◼◻◼◻◻◼◻◼  (79)
  ◼◻◼◻◼◻◻◻◼◼  (80)
  ◼◻◼◻◻◼◼◼◻◻  (81)
  ◼◻◼◻◻◼◼◻◼◻  (82)
  ◼◻◼◻◻◼◼◻◻◼  (83)
  ◼◻◼◻◻◼◻◼◼◻  (84)
  ◼◻◼◻◻◼◻◼◻◼  (85)
  ◼◻◼◻◻◼◻◻◼◼  (86)
  ◼◻◼◻◻◻◼◼◼◻  (87)
  ◼◻◼◻◻◻◼◼◻◼  (88)
  ◼◻◼◻◻◻◼◻◼◼  (89)
  ◼◻◼◻◻◻◻◼◼◼  (90)
  ◼◻◻◼◼◼◼◻◻◻  (91)
  ◼◻◻◼◼◼◻◼◻◻  (92)
  ◼◻◻◼◼◼◻◻◼◻  (93)
  ◼◻◻◼◼◼◻◻◻◼  (94)
  ◼◻◻◼◼◻◼◼◻◻  (95)
  ◼◻◻◼◼◻◼◻◼◻  (96)
  ◼◻◻◼◼◻◼◻◻◼  (97)
  ◼◻◻◼◼◻◻◼◼◻  (98)
  ◼◻◻◼◼◻◻◼◻◼  (99)
  ◼◻◻◼◼◻◻◻◼◼  (100)
  ◼◻◻◼◻◼◼◼◻◻  (101)
  ◼◻◻◼◻◼◼◻◼◻  (102)
  ◼◻◻◼◻◼◼◻◻◼  (103)
  ◼◻◻◼◻◼◻◼◼◻  (104)
  ◼◻◻◼◻◼◻◼◻◼  (105)
  ◼◻◻◼◻◼◻◻◼◼  (106)
  ◼◻◻◼◻◻◼◼◼◻  (107)
  ◼◻◻◼◻◻◼◼◻◼  (108)
  ◼◻◻◼◻◻◼◻◼◼  (109)
  ◼◻◻◼◻◻◻◼◼◼  (110)
  ◼◻◻◻◼◼◼◼◻◻  (111)
  ◼◻◻◻◼◼◼◻◼◻  (112)
  ◼◻◻◻◼◼◼◻◻◼  (113)
  ◼◻◻◻◼◼◻◼◼◻  (114)
  ◼◻◻◻◼◼◻◼◻◼  (115)
  ◼◻◻◻◼◼◻◻◼◼  (116)
  ◼◻◻◻◼◻◼◼◼◻  (117)
  ◼◻◻◻◼◻◼◼◻◼  (118)
  ◼◻◻◻◼◻◼◻◼◼  (119)
  ◼◻◻◻◼◻◻◼◼◼  (120)
  ◼◻◻◻◻◼◼◼◼◻  (121)
  ◼◻◻◻◻◼◼◼◻◼  (122)
  ◼◻◻◻◻◼◼◻◼◼  (123)
  ◼◻◻◻◻◼◻◼◼◼  (124)
  ◼◻◻◻◻◻◼◼◼◼  (125)
  ◻◼◼◼◼◼◻◻◻◻  (126)
  ◻◼◼◼◼◻◼◻◻◻  (127)
  ◻◼◼◼◼◻◻◼◻◻  (128)
  ◻◼◼◼◼◻◻◻◼◻  (129)
  ◻◼◼◼◼◻◻◻◻◼  (130)
  ◻◼◼◼◻◼◼◻◻◻  (131)
  ◻◼◼◼◻◼◻◼◻◻  (132)
  ◻◼◼◼◻◼◻◻◼◻  (133)
  ◻◼◼◼◻◼◻◻◻◼  (134)
  ◻◼◼◼◻◻◼◼◻◻  (135)
  ◻◼◼◼◻◻◼◻◼◻  (136)
  ◻◼◼◼◻◻◼◻◻◼  (137)
  ◻◼◼◼◻◻◻◼◼◻  (138)
  ◻◼◼◼◻◻◻◼◻◼  (139)
  ◻◼◼◼◻◻◻◻◼◼  (140)
  ◻◼◼◻◼◼◼◻◻◻  (141)
  ◻◼◼◻◼◼◻◼◻◻  (142)
  ◻◼◼◻◼◼◻◻◼◻  (143)
  ◻◼◼◻◼◼◻◻◻◼  (144)
  ◻◼◼◻◼◻◼◼◻◻  (145)
  ◻◼◼◻◼◻◼◻◼◻  (146)
  ◻◼◼◻◼◻◼◻◻◼  (147)
  ◻◼◼◻◼◻◻◼◼◻  (148)
  ◻◼◼◻◼◻◻◼◻◼  (149)
  ◻◼◼◻◼◻◻◻◼◼  (150)
  ◻◼◼◻◻◼◼◼◻◻  (151)
  ◻◼◼◻◻◼◼◻◼◻  (152)
  ◻◼◼◻◻◼◼◻◻◼  (153)
  ◻◼◼◻◻◼◻◼◼◻  (154)
  ◻◼◼◻◻◼◻◼◻◼  (155)
  ◻◼◼◻◻◼◻◻◼◼  (156)
  ◻◼◼◻◻◻◼◼◼◻  (157)
  ◻◼◼◻◻◻◼◼◻◼  (158)
  ◻◼◼◻◻◻◼◻◼◼  (159)
  ◻◼◼◻◻◻◻◼◼◼  (160)
  ◻◼◻◼◼◼◼◻◻◻  (161)
  ◻◼◻◼◼◼◻◼◻◻  (162)
  ◻◼◻◼◼◼◻◻◼◻  (163)
  ◻◼◻◼◼◼◻◻◻◼  (164)
  ◻◼◻◼◼◻◼◼◻◻  (165)
  ◻◼◻◼◼◻◼◻◼◻  (166)
  ◻◼◻◼◼◻◼◻◻◼  (167)
  ◻◼◻◼◼◻◻◼◼◻  (168)
  ◻◼◻◼◼◻◻◼◻◼  (169)
  ◻◼◻◼◼◻◻◻◼◼  (170)
  ◻◼◻◼◻◼◼◼◻◻  (171)
  ◻◼◻◼◻◼◼◻◼◻  (172)
  ◻◼◻◼◻◼◼◻◻◼  (173)
  ◻◼◻◼◻◼◻◼◼◻  (174)
  ◻◼◻◼◻◼◻◼◻◼  (175)
  ◻◼◻◼◻◼◻◻◼◼  (176)
  ◻◼◻◼◻◻◼◼◼◻  (177)
  ◻◼◻◼◻◻◼◼◻◼  (178)
  ◻◼◻◼◻◻◼◻◼◼  (179)
  ◻◼◻◼◻◻◻◼◼◼  (180)
  ◻◼◻◻◼◼◼◼◻◻  (181)
  ◻◼◻◻◼◼◼◻◼◻  (182)
  ◻◼◻◻◼◼◼◻◻◼  (183)
  ◻◼◻◻◼◼◻◼◼◻  (184)
  ◻◼◻◻◼◼◻◼◻◼  (185)
  ◻◼◻◻◼◼◻◻◼◼  (186)
  ◻◼◻◻◼◻◼◼◼◻  (187)
  ◻◼◻◻◼◻◼◼◻◼  (188)
  ◻◼◻◻◼◻◼◻◼◼  (189)
  ◻◼◻◻◼◻◻◼◼◼  (190)
  ◻◼◻◻◻◼◼◼◼◻  (191)
  ◻◼◻◻◻◼◼◼◻◼  (192)
  ◻◼◻◻◻◼◼◻◼◼  (193)
  ◻◼◻◻◻◼◻◼◼◼  (194)
  ◻◼◻◻◻◻◼◼◼◼  (195)
  ◻◻◼◼◼◼◼◻◻◻  (196)
  ◻◻◼◼◼◼◻◼◻◻  (197)
  ◻◻◼◼◼◼◻◻◼◻  (198)
  ◻◻◼◼◼◼◻◻◻◼  (199)
  ◻◻◼◼◼◻◼◼◻◻  (200)
  ◻◻◼◼◼◻◼◻◼◻  (201)
  ◻◻◼◼◼◻◼◻◻◼  (202)
  ◻◻◼◼◼◻◻◼◼◻  (203)
  ◻◻◼◼◼◻◻◼◻◼  (204)
  ◻◻◼◼◼◻◻◻◼◼  (205)
  ◻◻◼◼◻◼◼◼◻◻  (206)
  ◻◻◼◼◻◼◼◻◼◻  (207)
  ◻◻◼◼◻◼◼◻◻◼  (208)
  ◻◻◼◼◻◼◻◼◼◻  (209)
  ◻◻◼◼◻◼◻◼◻◼  (210)
  ◻◻◼◼◻◼◻◻◼◼  (211)
  ◻◻◼◼◻◻◼◼◼◻  (212)
  ◻◻◼◼◻◻◼◼◻◼  (213)
  ◻◻◼◼◻◻◼◻◼◼  (214)
  ◻◻◼◼◻◻◻◼◼◼  (215)
  ◻◻◼◻◼◼◼◼◻◻  (216)
  ◻◻◼◻◼◼◼◻◼◻  (217)
  ◻◻◼◻◼◼◼◻◻◼  (218)
  ◻◻◼◻◼◼◻◼◼◻  (219)
  ◻◻◼◻◼◼◻◼◻◼  (220)
  ◻◻◼◻◼◼◻◻◼◼  (221)
  ◻◻◼◻◼◻◼◼◼◻  (222)
  ◻◻◼◻◼◻◼◼◻◼  (223)
  ◻◻◼◻◼◻◼◻◼◼  (224)
  ◻◻◼◻◼◻◻◼◼◼  (225)
  ◻◻◼◻◻◼◼◼◼◻  (226)
  ◻◻◼◻◻◼◼◼◻◼  (227)
  ◻◻◼◻◻◼◼◻◼◼  (228)
  ◻◻◼◻◻◼◻◼◼◼  (229)
  ◻◻◼◻◻◻◼◼◼◼  (230)
  ◻◻◻◼◼◼◼◼◻◻  (231)
  ◻◻◻◼◼◼◼◻◼◻  (232)
  ◻◻◻◼◼◼◼◻◻◼  (233)
  ◻◻◻◼◼◼◻◼◼◻  (234)
  ◻◻◻◼◼◼◻◼◻◼  (235)
  ◻◻◻◼◼◼◻◻◼◼  (236)
  ◻◻◻◼◼◻◼◼◼◻  (237)
  ◻◻◻◼◼◻◼◼◻◼  (238)
  ◻◻◻◼◼◻◼◻◼◼  (239)
  ◻◻◻◼◼◻◻◼◼◼  (240)
  ◻◻◻◼◻◼◼◼◼◻  (241)
  ◻◻◻◼◻◼◼◼◻◼  (242)
  ◻◻◻◼◻◼◼◻◼◼  (243)
  ◻◻◻◼◻◼◻◼◼◼  (244)
  ◻◻◻◼◻◻◼◼◼◼  (245)
  ◻◻◻◻◼◼◼◼◼◻  (246)
  ◻◻◻◻◼◼◼◼◻◼  (247)
  ◻◻◻◻◼◼◼◻◼◼  (248)
  ◻◻◻◻◼◼◻◼◼◼  (249)
  ◻◻◻◻◼◻◼◼◼◼  (250)
  ◻◻◻◻◻◼◼◼◼◼  (251)

    (Finishes in 26 ms on an old laptop.)

逻辑

基本步骤：

  • 创建一个长度为m的索引数组，初始化为第一组合。 初始组合是由不同元素组成的组合数组，
  • 在循环中，
    • 增加最后一个索引(即m-1)，直到n-1， 每次增加都会得到一组新的组合。
    • 当最后一个索引变为n-1时，在循环中，
      • 增加前面一个索引；
      • 如果这两个索引相连，则将当前和上一个向左移动1位，然后继续增加， 每次增加都会得到一组新的组合；
      • 否则，将相连的后缀移到与未连接的那一个后面， 移动后，将得到一组新的组合，

循环结束：

  • 在增加前一个索引后，如果它的索引为0，并且是最高可能的值(即n-m)，则完成；

特殊情况：

  • 如果m = 1，则无需增加前一个索引，否则会导致超出索引范围(-1)；
  • 如果m = n，则只需要返回初始组合；

提示

  • 我通过检查https://www.baeldung.com/cs/generate-k-combinations#comparison中的第一个图表，该图表来自于《计算机程序设计艺术》第4A卷（2011年），找到了如何做到这一点。
  • 与我编写的另一个递归版本相比，这段代码更复杂，但对于大型输入，它更快。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接