更新: 我将这个问题作为一系列文章的主题,从这里开始; 在那个系列中,我会介绍两种略有不同的算法。感谢这个好问题!
到目前为止发布的两个解决方案对于数字变大的情况来说是正确但效率低下的。 到目前为止发布的解决方案使用的算法是:首先枚举所有可能性:
{1, 1, 1 }
{1, 1, 2 },
{1, 1, 3 },
...
{7, 7, 7}
在这个过程中,筛选出第二个数不大于第一个数,第三个数不大于第二个数的所有数字。这将执行7 x 7 x 7个筛选操作,数量并不是很多,但是如果你想从30个元素中获取10个元素的排列,那么就需要进行30 x 30 x 30 x 30 x 30 x 30 x 30 x 30 x 30 x 30个筛选操作,这是相当多的。你可以做得更好。
我会按照以下方式解决这个问题。首先,创建一个高效的不可变集合数据结构。让我非常清楚地说明一下什么是不可变集合,因为你可能不熟悉它们。通常,你认为集合是可以添加和删除元素的。但是不可变集合具有Add
操作,但它不会更改集合;它会返回一个新的集合,其中包含了添加了该项的元素。移除也是同样。
这里是一个实现整数0到31的不可变集合的示例:
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System;
internal struct BitSet : IEnumerable<int>
{
public static BitSet Empty { get { return default(BitSet); } }
private readonly int bits;
private BitSet(int bits) { this.bits = bits; }
public bool Contains(int item)
{
Debug.Assert(0 <= item && item <= 31);
return (bits & (1 << item)) != 0;
}
public BitSet Add(int item)
{
Debug.Assert(0 <= item && item <= 31);
return new BitSet(this.bits | (1 << item));
}
public BitSet Remove(int item)
{
Debug.Assert(0 <= item && item <= 31);
return new BitSet(this.bits & ~(1 << item));
}
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
public IEnumerator<int> GetEnumerator()
{
for(int item = 0; item < 32; ++item)
if (this.Contains(item))
yield return item;
}
public override string ToString()
{
return string.Join(",", this);
}
}
仔细阅读此代码,了解其工作原理。请记住,向此集合添加元素不会改变该集合。它会生成 一个新的集合,其中包含添加的项。
好的,既然我们明白了这一点,让我们考虑一个更高效的算法来生成排列。
我们将通过递归方法来解决问题。递归解决方案始终具有相同的结构:
- 我们可以解决一个微不足道的问题吗?如果可以,请解决它。
- 如果不能,请将问题分解为若干个较小的问题,并解决每个问题。
让我们从微不足道的问题开始。
假设您有一个集合,希望从中选择零项。答案很清楚:有且只有一个可能的排列,即空集。
假设您有一个包含n个元素的集合,并且您想选择超过n个元素。显然没有解决方案,甚至连空集都没有。
现在我们已经处理了集合为空或所选元素数量大于总元素数量的情况,因此我们必须从至少有一个元素的集合中选择至少一件事。
在可能的排列中,一些排列中包含第一个元素,而另一些排列则不包含。找出所有包含第一个元素的排列并产生它们。我们通过在缺少第一个元素的集合上递归地选择较少的一个元素来实现这一点。
我们通过枚举没有第一个元素的集合的排列,找到不包含第一个元素的排列。
static class Extensions
{
public static IEnumerable<BitSet> Choose(this BitSet b, int choose)
{
if (choose < 0) throw new InvalidOperationException();
if (choose == 0)
{
yield return BitSet.Empty;
}
else if (b.Count() >= choose)
{
int first = b.First();
BitSet rest = b.Remove(first);
foreach(BitSet r in rest.Choose(choose-1))
yield return r.Add(first);
foreach(BitSet r in rest.Choose(choose))
yield return r;
}
}
}
现在我们可以问你需要答案的问题:
class Program
{
static void Main()
{
BitSet b = BitSet.Empty.Add(1).Add(2).Add(3).Add(4).Add(5).Add(6).Add(7);
foreach(BitSet result in b.Choose(3))
Console.WriteLine(result);
}
}
我们完成了。我们只生成了实际需要的序列。(尽管我们进行了许多集合操作,但是集合操作很便宜。)这里的要点是理解这个算法的工作原理非常有教益。对于许多专业程序员来说,递归编程和不可变结构是一种强大的工具,他们的工具箱中可能没有这些知识。