组合问题 [英] Combinations problem

问题描述

大家好，

我有一系列值，我想生成所有可能的

组合。并且示例将是值a，b，c。这将是
产生以下内容：


a

ab

abc

ac

b

bc

c


有谁知道产生此算法的算法？我已经看过讨论过的主题

，但从来没有用过字符串或其他任何东西。大多数讨论

是关于计算组合的数量...我不在乎

约。


谢谢提前，

Tom Cameron

tom< at> drdabbles< dot> us

-

comp。 lang.c.moderated - 审核地址： cl**@plethora.net - 你必须

有一个适当的新闻组在您的标题中排列，以便查看您的邮件，

或主题行中方括号中的新闻组名称。对不起。

Hello all,
I have an array of values which I would like to generate all possible
combinations for. And example would be the values "a,b,c". This would
produce the following:

a
ab
abc
ac
b
bc
c

Does anybody know of the algorithm to produce this? I''ve seen the topic
discussed, but never for strings or anything of the such. Most discussion
is regarding calculating the number of combinations...which I don''t care
about.

Thanks in advance,
Tom Cameron
tom<at>drdabbles<dot>us
--
comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

推荐答案

你需要的是一种置换算法。如果你有一大套

项目，那就意味着漫长的等待。但如果你的套装很小，那么它的全部是木头。只需查看左侧的添加内容，您就可以查看
www.cs.sunysb。 edu 了解更多信息。然后将您的NULL终止（

course）char数组传递给函数U create。如果你需要更多的帮助，

只需要问.....

what you need is a permutation algorithm. If you have a large set of
items then that means a long wait. but if your set is small then its
all wood. Just looking at the adds on the left you could check out
www.cs.sunysb.edu to learn more. Then pass your NULL terminated ( of
course) char array to the function U create. If you need more help,
just ask.....

Thomas Cameron写道：

Thomas Cameron wrote:

大家好，
我有一系列值，我想生成所有可能的组合。并且示例将是值a，b，c。这将产生以下结果：

ab
abc
ac
b
bc
c

有谁知道生成这个的算法？我已经看到了讨论过的主题，但从来没有看过字符串或其他任何内容。大多数讨论
是关于计算组合的数量...我不在乎


提前致谢，汤姆卡梅隆 tom< at> drdabbles< dot> us
-
comp.lang.c.moderated - 审核地址： cl ** @ plethora.net - 您必须在标题中有适当的新闻组行，以便查看您的邮件，
或主题行中方括号中的新闻组名称。抱歉。

Hello all,
I have an array of values which I would like to generate all possible
combinations for. And example would be the values "a,b,c". This would
produce the following:

a
ab
abc
ac
b
bc
c

Does anybody know of the algorithm to produce this? I''ve seen the topic
discussed, but never for strings or anything of the such. Most discussion
is regarding calculating the number of combinations...which I don''t care
about.

Thanks in advance,
Tom Cameron
tom<at>drdabbles<dot>us
--
comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line. Sorry.

Thomas Cameron写道：

Thomas Cameron wrote:

我有一系列值我想生成所有可能的
组合。并且示例将是值a，b，c。这将产生以下结果：
a
abc
ac
b
bc
c
有谁知道产生这个的算法？

I have an array of values which I would like to generate all possible
combinations for. And example would be the values "a,b,c". This would
produce the following:
a
ab
abc
ac
b
bc
c
Does anybody know of the algorithm to produce this?

我很确定这个必须在Knuth中涵盖，如果不是更早的话

那么第4卷的初步介绍之一。


无论如何，很容易搞清楚。让我们假设所有的

数组值是不同的，或者如果不是你想要生成的

重复数据。 （否则，首先排序

数组然后走它并将其折叠为一个实例
每个
。）那么你想要的是：

，以确定每个元素是否存在于集合中。

因所有可能的组合而异。这应该响铃铃声：存在= 1，缺席= 0 =>宽度的二进制整数

N其中N =＃elements。因此，您所要做的就是枚举N位整数的不同可能性，这可以简单地通过计数从0开始完成。对于每个值

计数器，滑过1位经过它，并确定

相应的位置是否表示存在

或缺席那个元素。如果存在，则输出令牌;

如果不存在，则不执行任何操作。在1位滑动N位后，

输出换行并增加计数器。注意，这个

也会输出空字符串（没有元素存在），

是一个有效的组合但是你可能想要消除

（所以在1开始计数器）。

I''m pretty sure this must be covered in Knuth, if not earlier
then in one of the preliminary facsicles for Volume 4.

Anyway, it is easy to figure out. Let''s assume that all the
array values are distinct, or if not that you want the
duplicates that will be produced. (Otherwise, first sort
the array then walk it and collapse it down to one instance
each.) Then what you want can be characterized by: sets
such that whether or not each element is present in the set
varies through all possible combinations. That should ring
a bell: presence = 1, absence = 0 => binary integer of width
N where N = # elements. Thus all you have to do is enumerate
the distinct possibilities for an N-bit integer, which can be
done simply by counting, starting at 0. For each value of
the counter, slide a 1-bit past it, ANDing to determine
whether or not the corresponding position denotes the presence
or the absence of that element. If present, output the token;
if absent, do nothing. After the 1-bit has been slid N places,
output a newline and increment the counter. Note that this
will also output the empty string (no element present), which
is a valid combination but which you might want to eliminate
(so start the counter at 1 instead).

这篇关于组合问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！