这是一个关于非数学家的组合学的问题,所以请尽量忍受我!
给定n个不同字符的数组,我想以最小变化顺序生成k个字符的子集,即生成i + 1恰好包含一个不在第i代中的字符的顺序.这本身并不太难.不过,我也希望最大化病例数在被换角色了在代I + 1是被交换相同的字符中的代我.为了说明,对于n = 7,k = 3:
abc abd abe*abf*abg*afg aeg*adg*acg*acd ace*acf*aef adf*ade bde bdf bef bcf*bce bcd*bcg*bdg beg*bfg*cfg ceg*cdg*cde cdf*cef def deg dfg efg
带星号的字符串表示我想要最大化的情况; 例如,第3代中新增的e,abe,替换第2代中的新广告,abd.似乎不可能在每一代都发生这种情况,但我希望它尽可能频繁地发生.
我使用的典型阵列大小是20-30,子集大小大约5-8.
我使用的是奇怪的语言,Icon(或者实际上是它的衍生Unicon),所以我不希望任何人发布我可以直接使用的代码.但我会很感激伪代码的答案或提示,并会尽力翻译C等.另外,我注意到这类问题经常以整数数组的形式讨论,我当然可以应用解决方案以这样的方式发布我自己的问题.
谢谢
金巴斯汀
编辑2010年6月15日:
我似乎进入了比我想象的更深的水,虽然我很感激所有答案,但并非所有答案都相关.作为一个不充分的解决方案的例子,让我发布我自己的Unicon程序,以最小的变化顺序生成字符集的k元子集.要理解代码,你需要知道的事情是:前置*表示结构的大小,所以如果s是字符串,*s表示s的大小(它包含的字符数).|| 是一个字符串连接操作.一个前置!产生结构的每个元素,例如字符串的每个字符,依次连续传递.'suspend'控制结构返回一个过程的结果,但是将过程"悬浮",所有局部变量就位,这样如果在循环中调用过程,就可以产生新的结果.
procedure revdoor(s, k)
# Produces all k-subsets of a string or character set s in a 'revolving
# door' order. Each column except the first traverses the characters
# available to it in alphabetical and …