c - 是否有一种算法可以打印数组子序列的所有排列？

Question

我正在研究组合学，我想知道是否有一种算法可以打印给定数组的子序列的所有排列。也就是说，如果我为该算法提供序列“ABCDEF”，它将打印:

一个, 乙, C， , 乙， F,
AB, 空调， 广告， 不良事件, 自动对焦， 公元前， 屋宇署， 是， 高炉, 光盘， 行政长官， CF, 德， 东风, 英孚，
美国广播公司, ABD, 安倍， ABF, 交流电， 高手， active 碳纤维， 阿德， 自动进纸器， AEF, BCD, 公元前， 生物浓缩系数， 溴化二苯醚， 背离， 绝地求生, 开发环境， 发展基金、 基金， 防御，
A B C D， ABCE， 商业银行, 苯二甲醚， ABDF， ABEF， , ACDF， 中华环保 union 会， ADEF， BCDE, BCDF, BCEF, BDEF, CDEF,
ABCDE, ABCDF, 美国农业部， ABDEF， 亚洲发展基金， BCDEF， ABCDEF,

或者对于更简单的情况，如果我给它 1234，它会打印:

1,2,3,4,12,13,14,23,24,34,123,124,134,234,1234。

如您所见，它不是任意排列，它只是子序列最后一个成员的排列，其方式仍然是子序列。

我试图在 c 中创建一个函数来执行此操作，但我真的很困惑，我的想法是创建一个 int L 来保持子序列的大小，另一个树整数来保持子序列的头部，一个标志着与头部的分离，一个在给定数量的字符中滑动，但它很快就会变得太困惑。

谁能帮我解决这个问题？

我的代码是:

int Stringsize( char m[] ){

     int k;
     for(k=0;;k++){
     if( m[k] == '\0') break;    
     }
return (k-1);

}


void StringOrdM(char m[]){
    int q,r,s,k; 
    for(k=0;k<=Stringsize(m);k++)
       for(q=0;q<=Stringsize(m);q++)
          for(s=q;s<=Stringsize(m);s++ )
              printf("%c",m[q]);
          for(r=q+1; r<=Stringsize(m) && (r-q+1)<= k ;r++ )
              printf("%c", m[r] );

}

对于 ABCD，它打印 A,A,A,A,B,B,B,C,C,D,AA,AB,AC,AD,BC,BD,CC,CD,DD,... 所以这是不对的，因为它一直将 A 重复 4 次，将 B 重复 3 次，依此类推，而应该是 A、B、C、D、AB、AC、AD、BC、BD、CD、...

Answer 1

正如我在上面的评论中所说，一种解决方案很简单:用二进制数最多为 (1<<n)-1。 .

因此，如果您有四个项目，数到 15 个，每个位模式都是元素的选择。你会得到 0001 , 0010 , 0011 , 0100 , 0101 , 0110 , 0111 , 1000 , 1001 , 1010 , 1011 , 1100 , 1101 , 1110 , 1111 .每个位都是关于是否包含该数组元素的真/假值。

#include <stdio.h>

int main(void) {
  ////////////////////////////////////////////////////////////////////////
  int A[] = { 1, 2, 3, 4, 5 };
  ////////////////////////////////////////////////////////////////////////

  size_t len = sizeof A / sizeof A[0];    // Array length (in elements)
  size_t elbp = (1<<len) - 1;             // Element selection bit pattern
  size_t i, j;                            // Iterators

  // Cycle through all the bit patterns
  for (i = 1; i<=elbp; i++) {
    // For each bit pattern, print out the 'checked' elements
    for (j = 0; j < len; j++) {
      if (i & (1<<j)) printf("%d ", A[j]);
    }
    printf("\n");
  }

  return 0;
}

如果您希望元素从最短到最长排序，您始终可以将这些结果存储在字符串数组中(使用 sprintf() )，然后按字符串长度排序(使用稳定的排序算法!)。