最小化"交换"的最小变化算法

Question

这是一个关于非数学家的组合学的问题,所以请尽量忍受我!

给定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 reverse alphabetical order  
# alternately. The order of the input string is preserved. 
# If called in a loop as revdoor("abcdefg", 3), 
# the order of production is: abc, abd, abe, abf, abg, acg, acf, ace, acd,  
# ade, adf, adg, aeg, aef, afg, bfg, bef, beg, bdg, bdf, bde, bcd, bce,  
# bcf, bcg, cdg, cdf, cde, cef, ceg, cfg, dfg, deg, def, efg  

local i  
static Ctl  

if /Ctl then {             # this means 'if Ctl doesn't exist'
  if k = 0 then return ""  
  Ctl := list(k, 1)        # a list of k elements, each initialised to 1.
}  

if Ctl[k] = 1 then {  
  if k = 1 then suspend !s else  
    every i := 1 to *s-k+1 do {  
      suspend s[i] || revdoor(s[i+1:0], k-1)  
    }   
  } else {  
    if k = 1 then suspend !reverse(s) else  
    every i := -k to -*s by -1 do {  
      suspend s[i] || revdoor(s[i+1:0], k-1)  
    }  
  }  

  # the following line multiplies element k of Ctl by -1 if k < size of Ctl
  # (this controls the order of generation of characters), 
  # and destroys Ctl on final exit from the procedure.
  if k < *Ctl then Ctl[k] *:= -1 else Ctl := &null   

end  

请注意,上述过程的输出在我看来并不是最佳的.到目前为止,我调查的一个结果是,n个元素的k元子集列表的最大"交换分数"不小于comb(n-1,k),或者在n = 7的情况下,k =在图3中,最大分数至少是comb(6,3)= 20.我将列表的"交换分数"定义为列表中的项目数,其中新元素替换上一项中本身是新的元素.我没有数学设备来证明这一点,但很容易看出k = 1或k = 2.对于某些(n,k),可能会有更高的分数,如n = 7,k = 3的情况:

abc abd abe abf abg
acg adg aeg afg
efg dfg cfg bfg
beg bdg bcg
bcd bce bcf
bdf bef
def cef aef
adf acf
acd ace
ade
bde cde
cdf
cdg ceg
deg(swapping score = 21)

可以注意到,上面的列表是"强烈的最小变化顺序"(比如单词高尔夫:新角色总是与它所替换的角色处于相同的位置),这可以指示我自己的工作所采取的方向.我希望在几天内发布更多内容.

金

Answer 1

这相当简单。为了最大化替换，只需将字符视为数字并将字符串加一，直到达到上限。然后检查并确保您没有在字符串中使用相同的字符两次。我认为这会起作用：

char c[] = {'a', 'b', 'c', 'd', 'e'};
const int n = 5;
const int k = 3;
char s[k];

void print()
{
    for( int i = 0; i < k; ++i )
        putchar(c[s[i]]);
    putchar('\n');
}

bool increment( int m )
{
    // reached the limit?
    if( ++s[m] == n && m == 0 )
        return false;

    next:   
    for( int i = 0; i < m; ++i )
    {
        if( s[m] == n )
        {
            // carry
            s[m] = 0;
            if( !increment( m-1 ))
                return false;
            goto next;
        }
        else if( s[i] == s[m] )
        {
            // the character is already used
            ++s[m];
            goto next;
        }   
    }
    return true;
}

int main(int, char**)
{   
    // initialise
    for( int i = 0; i < k; ++i )
        s[i] = i;

    // enumerate all combinations
    do
        print();
    while(increment(k-1));
}