生成所有可能的组合
我正在编写一些代码,并以此问题结束。我有N种产品,我必须形成这些产品的所有可能组合,形成产品目录并查找价格等一些属性。为了做到这一点,我必须从给定的产品形成产品目录(详尽,但不允许重复)。有没有一个标准化的算法来做到这一点?请注意,目录可以包含任何正数量的产品。生成所有可能的组合
计算机编程艺术的第一部分,第一卷。 3,Sorting and Searching详细讨论了反转和置换(集合和多集合)。在这种情况下,重要的是在理论上进行一点探索,看看有什么。代码将随之而来,但如果这是“闲暇时间编码”,为什么不包括“闲暇时间理论”呢? Betcha它会很酷,你会知道最新的情况,但你也会知道原因!
组合可以用位向量表示。如果设置了一个位,则该元素存在于组合中。
所以你只需要从1到2^N-1(0000001,最后一个存在的元素直到1111111,存在的所有元素)都能启动所有数字,并且表示可能的组合。
我使用整数(作为现在的数组索引)作为产品。有没有办法从这个设置开始,而不是编写新的代码:-( – Malice
等等,你是:-(关于纠正新代码? – quasiverse
好吧,如果你不想解码你可以实现你的数字自己的二进制增量(数组中的每个索引都是二进制数字),也可以使用一些聪明的灰色代码生成器来枚举所有数字http://en.wikipedia.org/wiki/Gray_code –
一个天真的实现打印字符的组合,都从一个给字符串:
void print_combination(char* str, char* buffer, int len, int num, int pos)
{
if(num == 0)
{
std::cout << buffer << std::endl;
return;
}
for(int i = pos; i < len - num + 1; ++i)
{
buffer[num - 1] = str[i];
print_combination(str, buffer, len, num - 1, i + 1);
}
}
int main()
{
char str[] = "abcde";
char buffer[6];
for(auto i = 1u; i <= sizeof(str); ++i)
{
buffer[i] = '\0';
print_combination(str, buffer, 5, i, 0);
}
}
很简单,但可能有性能问题。如果它可以帮助,就拿它。
如果你正在寻找置换(我无法从你的描述告诉),我实现的算法在计算机程序设计艺术:
template <typename Iter>
bool next_permutation(Iter start, Iter end)
{
if(start == end)
return false;
Iter i = start + 1;
if(i == end)
return false;
i = end - 1;
while(true)
{
Iter ii = i;
--i;
if(*i < *ii)
{
Iter j = end;
while(*i >= *--j);
std::iter_swap(i, j);
std::reverse(ii, end);
return true;
}
if(i == start)
{
std::reverse(start, end);
return false;
}
}
}
int main()
{
char str1[] = "abcde";
do
{
std::cout << str1 << std::endl;
} while(next_permutation(&str1[0], &str1[5]));
}
这是非常有效和C++ STL算法使用相同的算法。
第一个算法只打印5个字符的组合? – Malice
@Malice我在主函数中使用了一个循环来打印co 1,2,3,4,5个字符的组合。 –
你可以在Python做到这一点,在下列方式使用itertools.combinations:
import itertools
products = ['p1', 'p2', 'p3', 'p4']
for L in range(1, len(products)+1):
for subset in itertools.combinations(products, L):
print(subset)
什么让作为结果:
('p1',)
('p2',)
('p3',)
('p4',)
('p1', 'p2')
('p1', 'p3')
('p1', 'p4')
('p2', 'p3')
('p2', 'p4')
('p3', 'p4')
('p1', 'p2', 'p3')
('p1', 'p2', 'p4')
('p1', 'p3', 'p4')
('p2', 'p3', 'p4')
('p1', 'p2', 'p3', 'p4')
解决方案通过this answer of @dan-h启发。
排列=订单事项(有序列表)。组合=顺序无关紧要(一组)。 –
好的。那么我猜这是组合 – Malice
如果它是一个组合,你可以这样做:'为i = 1到2^N'并使用位hax ...我认为... – quasiverse