我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
简短的python代码,产生索引位置
def yield_combos(n,k):
# n is set size, k is combo size
i = 0
a = [0]*k
while i > -1:
for j in range(i+1, k):
a[j] = a[j-1]+1
i=j
yield a
while a[i] == i + n - k:
i -= 1
a[i] += 1
其他回答
最近在IronScripter网站上有一个PowerShell挑战,需要一个n- choice -k的解决方案。我在那里发布了一个解决方案,但这里有一个更通用的版本。
AllK开关用于控制输出是长度为ChooseK的组合,还是长度为1到ChooseK的组合。 Prefix参数实际上是输出字符串的累加器,但其效果是为初始调用传递的值实际上会为每一行输出添加前缀。
function Get-NChooseK
{
[CmdletBinding()]
Param
(
[String[]]
$ArrayN
, [Int]
$ChooseK
, [Switch]
$AllK
, [String]
$Prefix = ''
)
PROCESS
{
# Validate the inputs
$ArrayN = $ArrayN | Sort-Object -Unique
If ($ChooseK -gt $ArrayN.Length)
{
Write-Error "Can't choose $ChooseK items when only $($ArrayN.Length) are available." -ErrorAction Stop
}
# Control the output
$firstK = If ($AllK) { 1 } Else { $ChooseK }
# Get combinations
$firstK..$ChooseK | ForEach-Object {
$thisK = $_
$ArrayN[0..($ArrayN.Length-($thisK--))] | ForEach-Object {
If ($thisK -eq 0)
{
Write-Output ($Prefix+$_)
}
Else
{
Get-NChooseK -Array ($ArrayN[($ArrayN.IndexOf($_)+1)..($ArrayN.Length-1)]) -Choose $thisK -AllK:$false -Prefix ($Prefix+$_)
}
}
}
}
}
例如:
PS C:\>$ArrayN = 'E','B','C','A','D'
PS C:\>$ChooseK = 3
PS C:\>Get-NChooseK -ArrayN $ArrayN -ChooseK $ChooseK
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
下面的递归算法从有序集中选取所有k元素组合:
选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。
对集合中的每一个i进行上述迭代。
为了避免重复,您必须选择比i大的其余元素。这样[3,5]将只被选中一次,即[3]与[5]结合,而不是两次(该条件消除了[5]+[3])。没有这个条件,你得到的是变化而不是组合。
Haskell中的简单递归算法
import Data.List
combinations 0 lst = [[]]
combinations n lst = do
(x:xs) <- tails lst
rest <- combinations (n-1) xs
return $ x : rest
我们首先定义特殊情况,即选择零元素。它产生一个单一的结果,这是一个空列表(即一个包含空列表的列表)。
对于n> 0, x遍历列表中的每一个元素xs是x之后的每一个元素。
Rest通过对组合的递归调用从xs中选取n - 1个元素。该函数的最终结果是一个列表,其中每个元素都是x: rest(即对于x和rest的每个不同值,x为头部,rest为尾部的列表)。
> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
当然,由于Haskell是懒惰的,列表是根据需要逐渐生成的,因此您可以部分计算指数级的大组合。
> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
"abcdefgo","abcdefgp","abcdefgq"]
这里你有一个用c#编写的该算法的惰性评估版本:
static bool nextCombination(int[] num, int n, int k)
{
bool finished, changed;
changed = finished = false;
if (k > 0)
{
for (int i = k - 1; !finished && !changed; i--)
{
if (num[i] < (n - 1) - (k - 1) + i)
{
num[i]++;
if (i < k - 1)
{
for (int j = i + 1; j < k; j++)
{
num[j] = num[j - 1] + 1;
}
}
changed = true;
}
finished = (i == 0);
}
}
return changed;
}
static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
{
T[] elem = elements.ToArray();
int size = elem.Length;
if (k <= size)
{
int[] numbers = new int[k];
for (int i = 0; i < k; i++)
{
numbers[i] = i;
}
do
{
yield return numbers.Select(n => elem[n]);
}
while (nextCombination(numbers, size, k));
}
}
及测试部分:
static void Main(string[] args)
{
int k = 3;
var t = new[] { "dog", "cat", "mouse", "zebra"};
foreach (IEnumerable<string> i in Combinations(t, k))
{
Console.WriteLine(string.Join(",", i));
}
}
希望这对你有帮助!
另一种版本,迫使所有前k个组合首先出现,然后是所有前k+1个组合,然后是所有前k+2个组合,等等。这意味着如果你对数组进行排序,最重要的在最上面,它会把它们逐渐扩展到下一个——只有在必须这样做的时候。
private static bool NextCombinationFirstsAlwaysFirst(int[] num, int n, int k)
{
if (k > 1 && NextCombinationFirstsAlwaysFirst(num, num[k - 1], k - 1))
return true;
if (num[k - 1] + 1 == n)
return false;
++num[k - 1];
for (int i = 0; i < k - 1; ++i)
num[i] = i;
return true;
}
例如,如果你在k=3, n=5上运行第一个方法("nextCombination"),你会得到:
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
但如果你跑
int[] nums = new int[k];
for (int i = 0; i < k; ++i)
nums[i] = i;
do
{
Console.WriteLine(string.Join(" ", nums));
}
while (NextCombinationFirstsAlwaysFirst(nums, n, k));
你会得到这个(为了清晰起见,我添加了空行):
0 1 2
0 1 3
0 2 3
1 2 3
0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4
它只在必须添加时才添加“4”,而且在添加“4”之后,它只在必须添加时再添加“3”(在执行01、02、12之后)。
我可以给出这个问题的递归Python解决方案吗?
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
使用示例:
>>> len(list(choose_iter("abcdefgh",3)))
56
我喜欢它的简洁。