8

これは非数学者からの組み合わせ論に関する質問なので、我慢してみてください!

n個の異なる文字の配列が与えられた場合、最小変更順序、つまり、世代i + 1に世代iになかった文字が1つだけ含まれる順序で、k個の文字のサブセットを生成したいと考えています。それ自体はさほど難しいことではありません。ただし、ジェネレーション i+1 でスワップアウトされたキャラクターが、ジェネレーション i でスワップインされたキャラクターと同じであるケースの数を最大化したいとも考えています。たとえば、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 であった ad を置き換えます。これをすべての世代で実現することは不可能に思えますが、可能な限り頻繁に実現したいと考えています。

私が使用する典型的な配列サイズは 20 ～ 30 で、サブセット サイズは 5 ～ 8 前後です。

私は奇妙な言語Icon (または実際にはその派生Unicon ) を使用しているため、私が直接使用できるコードを投稿する人はいないと思います。しかし、疑似コードでの回答やヒントに感謝し、C などの翻訳に最善を尽くします。また、この種の問題は整数の配列の観点から議論されることが多いことに気付きました。解決策を確実に適用できます。私自身の問題にそのような用語で投稿されました。

ありがとう

キム・バスティン

2010 年 6 月 15 日編集:

私は思っていたよりも深い水の中に入ったようです。すべての回答に感謝していますが、すべてが関連しているわけではありません. 適切ではない解決策の例として、最小限の変更順序で文字セット s の k-ary サブセットを生成するための私自身の Unicon 手順を投稿させてください。コードを理解するために知っておく必要があることは次のとおりです。前置された * は構造体のサイズを意味するため、s が文字列の場合、*s は s のサイズ (含まれる文字数) を意味します。|| 文字列連結操作です。前置き！構造体の各要素 (文字列の各文字など) を、連続するパスで順番に生成します。また、「サスペンド」制御構造はプロシージャから結果を返しますが、すべてのローカル変数が配置された状態でプロシージャを「サスペンド」のままにします。

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

上記の手順の出力は、私の感覚では最適ではないことに注意してください。これまでの調査結果の 1 つは、n 要素の k-ary サブセットのリストの最大「スワッピング スコア」は、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 (交換スコア = 21)

上記のリストは「強力な最小限の変更順序」(ゴルフという言葉のように: 新しいキャラクターは、置き換えられるキャラクターと常に同じ位置にある) であることに注意してください。数日中に何か投稿したいと思っています。

キム

4

5 に答える 5

1

それはかなり簡単です。置換を最大化するには、文字を数字と考えて、上限に達するまで文字列を 1 ずつ増やします。次に、文字列で同じ文字を 2 回使用していないことを確認します。私はこれがうまくいくと思います：

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));
}
于 2010-04-23T22:35:34.980 に答える
0

良い答えを得るには、組み合わせのリストを一度に計算することは許容されますか、それとも一度に 1 つずつ計算する必要がありますか? 言い換えれば、関数が必要ですか：

Combination nextCombo();

または

vector<Combination> allCombinations();

受け入れられる？

バッチでの組み合わせの計算が許容される場合、反復的な深化の A* 検索 (または単なる A* 検索ですが、メモリ不足になると思われます) が機能する可能性があります。許容可能なヒューリスティックにより、A* は最適値を与えることが保証されます。時間がないので、この部分的な回答を投稿し、コードを書く時間があれば投稿を編集することにしました。

A* はグラフ検索アルゴリズムです。この場合、ノードはこれまでに使用された組み合わせのリストです (リスト内での重複は許可されません)。私の計画は、ノードにビット文字列表現を使用することでした。n=30 は 32 ビット整数に収まります。最初の組み合わせが 0 で始まり 1 で終わる、つまり 000...1111 のように任意の解を並べ替えることができます。2 つのリストが最後の要素まで同じであり、最後の要素が 1 にフリップされた 0 ビットと 1 にフリップされた 1 ビットだけが異なる場合、短いリストを持つノードは長いリストに接続されます。 2 つの間の距離は、「スワップ」があった場合は 0、スワップがあった場合は 1 です。

各組み合わせの 2 番目の表現は、オンになっているビットのソート済みリストです。このグラフで許容できるヒューリスティックの 1 つは、このインデックス リストを使用することです。(組み合わせのリストで) インデックスがインデックス リストの特定の位置で使用されるたびに、それをマークします。未使用のインデックスを持つポジションの数 - 現在最後に変更されたインデックスは、(私が信じている) 必要なスワップの最小数です。

このヒューリスティックを説明するために、上から順に abc abd abe* abf* abg afg を考えてみましょう。(私の扱いでは文字は数字になりますが、それは小さな違いです)。このシーケンス (検索グラフの 1 つのノード) には、次の場所がマークされます。

1 2 3
*a      
 b*b   
 cc *c
 dd *d
 ええ*ええ
    *f *f
        *グラム

したがって、ヒューリスティックは、少なくとも 1 つのスワップが必要であると予測します (位置 3 にマークされていない要素がなく、現在の位置が 2 であるため)。

時間があれば、これを編集してコードとアルゴリズムのパフォーマンスを投稿します。

Re: NP 完全性の結果 (Zac Thompson の回答へのコメント)。最小コストのハミルトニアン パスを検索するグラフは、非常に特殊な構造を持っています。たとえば、通常 NP 完全なハミルトニアン パス問題は、「すべての組み合わせを列挙する」アルゴリズムを使用して O(n) 時間で解くことができます。n はグラフ内のノードの数です。この構造により、一般的なグラフでは頂点カバーが難しくても、グラフでは多項式 (線形または 2 次でさえ) になる可能性があります。もちろん、グラフには n=30、k=8 などの多数のノードがあるため、まだ多くの計算が必要になる場合があります。

于 2010-06-21T04:23:43.390 に答える
0

アルゴリズムから始めるのではなく、最大の「スワッピング スコア」のフォームを見つける方法を考えてみました。これにより、何を狙うかがわかります。多くの場合、目的の構造を生成するためのアルゴリズムは、そのような証明から生まれます。

大学時代から長い年月が経ちましたが、これを理解するのに役立つ組み合わせモデルを考えてみましたが、あまり運がありませんでした.

組み合わせのセットをグラフの頂点として想像することから始めました。エッジは組み合わせの「隣接性」(1 つの要素の違いのみ) に対応します。そう：

  • 「n 個の k 個の頂点を選択」
  • 各頂点には次数 k(nk) があります
  • エッジの数 = "n は k を選択" * k(nk) / 2 = "n は 2 を選択" * "n-2 は k-1 を選択"

これらのグラフには多くの対称性があります。任意の {n,k} のグラフは、{n,nk} のグラフと同じです。k=1 または k=n-1 の場合、それは n 個の頂点の完全なグラフです (各組み合わせは他のすべての組み合わせと 1 文字だけ異なります)。ただし、これから明らかなアルゴリズムはわかりません。

編集：私の次の考えは、わずかに異なる解釈でグラフを考えることでした. 各 {n,k} の組み合わせは、k 個の 1 がある n ビットのシーケンスと考えることができます。1 の位置は、組み合わせに存在する n 文字のどれに対応します。したがって、n=7 k=3 の場合、abc は 1110000、adg は 1001001、efg は 0000111 です。これにより、n 次元の超立方体の角にある点を想像することもできます。したがって、特定のサブシーケンスについて、エッジが同一平面上にある場合、エッジは「最小スワッピング」基準に一致します。私はそれらをハイパーキューブを通る「切断面」と考えています。

この組み合わせのグラフを介して、特別な基準を満たすハミルトニアン パスを探しています。

問題を考えるもう 1 つの方法は、シーケンス内で組み合わせのどの文字を変更するかを変更する回数を最小限に抑えることです。

于 2010-06-11T03:17:53.590 に答える
0

キム、あなたの問題の説明は、n 個の要素のセットのすべての k の組み合わせを列挙するための最も単純な解決策を説明しようとする (宿題) 試みのように聞こえますが、実際の解決策を簡単に説明することはありません。とにかく、私のショットについては以下を参照してください。Javaを使いましたが、重要な部分はCと変わりません。

public class Homework
{
  /**
   * Prints all k-combinations of a set of n elements. Answer to this 
   * question: http://stackoverflow.com/questions/2698551
   */
  public static void main(String[] args)
  {
    Combinations combinations = new Combinations(7, 3);
    System.out.printf(
        "Printing all %d %d-combinations of a set with %d elements:\n", 
        combinations.size(), combinations.k, combinations.n);
    for (int[] c : combinations)
      System.out.println(Arrays.toString(c));
  }

  /**
   * Provides an iterator for all k-combinations of a set of n elements. 
   */
  static class Combinations implements Iterable<int[]>  
  {
    public final int n, k;

    public Combinations(int n, int k)
    {
      if (n < 1 || n < k)
        throw new IllegalArgumentException();
      this.n = n;
      this.k = k;
    }

    @Override
    public Iterator<int[]> iterator()
    {
      return new Iterator<int[]>()
      {
        private int[] c;

        @Override
        public void remove() { throw new UnsupportedOperationException(); }

        @Override
        public int[] next()
        {
          if (c == null)
          {
            c = new int[k];
            for (int i = 0; i < k; i++)
              c[i] = i;
          }
          else
          {
            int i = c.length - 1;
            while (i >= 0 && c[i] == n - k + i)
              i--;

            if (i < 0)
              throw new NoSuchElementException();

            c[i]++;
            for (int j = i + 1; j < c.length; j++)
              c[j] = c[i] + j - i;
          }
          return c.clone(); // remove defensive copy if performance is more important
        }

        @Override
        public boolean hasNext() { return c == null || c[0] < n - k; }
      };
    }

    /**
     * Returns number of combinations: n! / (k! * (n - k)!).
     */
    public BigInteger size()
    {
      BigInteger s = BigInteger.valueOf(n);
      for (int i = n - 1; i > n - k; i--)
        s = s.multiply(BigInteger.valueOf(i));
      for (int i = k; i > 1; i--)
        s = s.divide(BigInteger.valueOf(i));
      return s;
    }
  }
}

あなたの例の出力は次のとおりです。

Printing all 35 3-combinations of a set with 7 elements:
[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 1, 6] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 2, 6] [0, 3, 4] 
[0, 3, 5] [0, 3, 6] [0, 4, 5] [0, 4, 6] [0, 5, 6] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 2, 6] [1, 3, 4] 
[1, 3, 5] [1, 3, 6] [1, 4, 5] [1, 4, 6] [1, 5, 6] [2, 3, 4] [2, 3, 5] [2, 3, 6] [2, 4, 5] [2, 4, 6] 
[2, 5, 6] [3, 4, 5] [3, 4, 6] [3, 5, 6] [4, 5, 6]
于 2010-05-02T17:22:24.593 に答える
0

私は 2010 年にこの問題に取り組みましたが、解決策を見つけることができませんでした。数日前、私は当時のメモをもう一度見て、解決に非常に近づいているのではないかと疑いました。数分後、私は鍵を手に入れました。

要約すると、要件は、LIFO (後入れ先出し) が最大化されるように、文字列 s の k-サブセットの厳密な最小変更順序です。以前の投稿では、これを最大化された「スワッピング」と呼んでいます。

キー要件の後に、このアルゴリズムを maxlifo (maximized LIFO) と呼びます。重複文字を含んではならない文字列 s と、s のサイズを超えない正の整数 k の 2 つのパラメータを取ります。このアルゴリズムは再帰的です。つまり、maxlifo(s, k) は maxlifo(s, k-1) の出力を k=1 まで使用します。出力はリストとして返されます。

以下に、文字列「abcdefg」とさまざまな k の値を使用して、例を挙げて非公式に説明します。続いて、Unicon プロシージャとしての実装例を示します。(私は、より一般的に使用されている言語に堪能ではありません。)

k=1 の場合は自明です — s の要素を最初から最後まで順番に返します。

k>1 の場合、次のルールを maxlifo(s, k-1) の出力に適用します。

(1) maxlifo(s, k-1) の出力の各要素について、その要素から構築された k-サブセットを s の各欠落文字を順番に並べてリストします。サブセット内の文字の順序は s と同じです。

(2) 2 番目の行から作業して、前の行に表示されるサブセットのすべての出現を空白の「プレースホルダー」に置き換えます。s の各 k-サブセットが 1 回だけ表示されるようになりました。

(3) 空白でない各行で、頭文字 ! でマークします。次の行の同じ位置にプレースホルダーがあるような各サブセット。このマークは「最初」を意味します。空白でない各行で、正確に 1 つのサブセットがそのようにマークされます。

(4) 完全に空白の行 (プレースホルダーのみを含む) をすべて削除します。

(5) 最後の行を除く残りの各行では、最後に ! を付けます。次の下の行で「最初」とマークされたサブセットに対応する位置のサブセット。このマーキングは「最後」を意味します。

これで、サブセットの maxlifo の最終的な順序を一覧表示できます。各行は上から下に並べられ、その要素がその順序で出力リストに追加されます。

(6) 各行の上から順に:

(6.1) 空白のプレースホルダーをすべて削除します。

(6.2) 出力リストに「最初」とマークされたサブセット (イニシャル !) を追加し、行から削除します。

(6.3) 行にまだサブセットが残っている場合、左端または右端のサブセットのいずれかが「最後」とマークされます (最終!)。右端のサブセットが「最後」とマークされている場合は、サブセットを左から右の順序で出力リストに追加します。それ以外の場合は、右から左の順序で追加します。

(7) すべての行を処理した後、出力リストを返します。

maxlifo("abcdefg", 2) を使用した例:

Col1 には maxlifo("abcdefg", 1) の出力が含まれます。Col2 の行には、s の残りの文字で形成されたクリークが含まれています。

Col1    Col2
----    ----------------------------
a       ab   ac   ad   ae   af   ag
b       ab   bc   bd   be   bf   bg
c       ac   bc   cd   ce   cf   cg
d       ad   bd   cd   de   df   dg
e       ae   be   ce   de   ef   eg
f       af   bf   cf   df   ef   fg
g       ag   bg   cg   dg   eg   fg

前の行に表示されるサブセットを空白にします。

a       ab   ac   ad   ae   af   ag
b            bc   bd   be   bf   bg
c                 cd   ce   cf   cg
d                      de   df   dg
e                           ef   eg
f                                fg
g

各行の「最初の」サブセット (下に空白があるもの) をマークします。

a      !ab   ac   ad   ae   af   ag
b           !bc   bd   be   bf   bg
c                !cd   ce   cf   cg
d                     !de   df   dg
e                          !ef   eg
f                               !fg
g

完全に空白の行をすべて削除します (この場合は 1 行だけ):

a      !ab   ac   ad   ae   af   ag
b           !bc   bd   be   bf   bg
c                !cd   ce   cf   cg
d                     !de   df   dg
e                          !ef   eg
f                               !fg

各行の「最後の」サブセット (その下に「最初の」サブセットがあるもの) をマークします。

a      !ab   ac!  ad   ae   af   ag
b           !bc   bd!  be   bf   bg
c                !cd   ce!  cf   cg
d                     !de   df!  dg
e                          !ef   eg!
f                               !fg

上記の順序で各行を出力します: 「最初」、マークなし、「最後」:

                                               Ordered rows:
a      !ab   ac!  ad   ae   af   ag            ab ag af ae ad ac
b           !bc   bd!  be   bf   bg            bc bg bf be bd
c                !cd   ce!  cf   cg            cd cg cf ce
d                     !de   df!  dg            de dg df
e                          !ef   eg!           ef eg
f                               !fg            fg

出力: [ab ag af ae ad ac bc bg bf be bd cd cg cf ce df dg de ef eg fg]

3 <= k <= 6 の例は、あまり詳細ではありません。手順 4 で削除された空白行はそのまま残ります。

maxlifo("abcdefg", 3):

                                                       Ordered rows:
ab     !abc   abd   abe   abf   abg!                   abc abd abe abf abg
ag            acg   adg   aeg! !afg                    afg acg adg aeg
af            acf   adf! !aef                          aef acf adf
ae            ace! !ade                                ade ace
ad           !acd!                                     acd
ac                     
bc           !bcd   bce   bcf   bcg!                   bcd bce bcf bcg
bg                  bdg   beg! !bfg                    bfg bdg beg
bf                  bdf! !bef                          bef bdf
be                 !bde!                               bde 
bd                                  
cd                 !cde   cdf   cdg!                   cde cdf cdg
cg                        ceg! !cfg                    cfg ceg
cf                       !cef!                         cef
ce                             
de                       !def   deg!                   def deg
dg                             !dfg!                   dfg
df                             
ef                             !efg                    efg
eg                       
fg

出力: [abc abd abe abf abg afg acg adg aeg aef acf adf ade ace acd
bcd bce bcf bcg bfg bdg beg bef bdf bde cde cdf cdg cfg ceg cef def deg dfg efg]

maxlifo("abcdefg", 4):

                                            Ordered rows:
abc         !abcd  abce!  abcf   abcg       abcd abcg abcf abce
abd               !abde   abdf!  abdg       abde abdg abdf
abe                      !abef   abeg!      abef abeg
abf                             !abfg!      abfg
abg                                   
afg                acfg!  adfg  !aefg       aefg adfg acfg
acg               !acdg   aceg!             acdg aceg
adg                      !adeg!             adeg
aeg                                  
aef                acef! !adef              adef acef
acf               !acdf!                    acdf
adf                                  
ade               !acde!                    acde
ace                                   
acd                                   
bcd               !bcde   bcdf!  bcdg       bcde bcdg bcdf
bce                      !bcef   bceg!      bcef bceg
bcf                             !bcfg!      bcfg
bcg                                  
bfg                       bdfg! !befg       befg bdfg
bdg                      !bdeg!             bdeg
beg                                  
bef                      !bdef!             bdef
bdf                                  
bde                                  
cde                      !cdef   cdeg!      cdef cdeg
cdf                             !cdfg!      cdfg
cdg                                   
cfg                             !cefg!      cefg
ceg                                  
cef                                  
def                             !defg       defg
deg                          
dfg                          
efg

出力: [abcd abcg abcf abce abde abdg abdf abef abeg abfg aefg adfg acfg acdg aceg adeg adef acef acdf acde bcde bcdg bcdf bcef bceg bcfg befg bdfg bdeg bdef cdef cdeg cdfg cefg defg]

maxlifo("abcdefg", 5):

                                            Ordered rows:
abcd       !abcde   abcdf   abcdg!          abcde abcdf abcdg 
abcg                abceg! !abcfg           abcfg abceg 
abcf               !abcef!                  abcef 
abce                                
abde               !abdef   abdeg!          abdef abdeg 
abdg                       !abdfg!          abdfg 
abdf                         
abef                       !abefg!          abefg 
abeg                         
abfg                         
aefg                acefg! !adefg           adefg acefg 
adfg               !acdfg!                  acdfg 
acfg                         
acdg               !acdeg!                  acdeg 
aceg                         
adeg                         
adef               !acdef!                  acdef 
acef                         
acdf                         
acde                         
bcde               !bcdef   bcdeg!          bcdef bcdeg 
bcdg                       !bcdfg!          bcdfg 
bcdf                         
bcef                       !bcefg!          bcefg 
bceg                         
bcfg                         
befg                       !bdefg!          bdefg 
bdfg                         
bdeg                         
bdef                         
cdef                       !cdefg           cdefg 
cdeg                         
cdfg                         
cefg                         
defg

出力: [abcde abcdf abcdg abcfg abceg abcef abdef abdeg abdfg abefg adefg acefg acdfg acdeg acdef bcdef bcdeg bcdfg bcefg bdefg cdefg]

maxlifo("abcdefg", 6):

                                            Ordered rows:
abcde               !abcdef   abcdeg!       abcdef abcdeg 
abcdf                        !abcdfg!       abcdfg 
abcdg                               
abcfg                        !abcefg!       abcefg 
abceg                              
abcef                               
abdef                        !abdefg!       abdefg 
abdeg                               
abdfg                               
abefg                               
adefg                               
acefg                        !acdefg!       acdefg 
acdfg                               
acdeg                               
acdef                               
bcdef                        !bcdefg        bcdefg 
bcdeg                               
bcdfg                               
bcefg                               
bdefg                               
cdefg

出力: [abcdef abcdeg abcdfg abcefg abdefg acdefg bcdefg]

ユニコンの実装:

procedure maxlifo(s:string, k:integer)
# A solution to my combinatorics problem from 2010.
# Return a list of the k subsets of the characters of a string s
# in a minimal change order such that last-in first-out is maximised.
# String s must not contain duplicate characters and in the present 
# implementation must not contain "!", which is used as a marker.

  local ch, cand, Hit, inps, i, j, K, L, Outp, R, S

  # Errors
  if *cset(s) ~= *s then 
    stop("Duplicate characters in set in maxlifo(", s, ", ", k, ")")
  if find("!", s) then 
    stop("Illegal character in set in maxlifo(", s, ", ", k, ")")
  if k > *s then 
    stop("Subset size larger than set size in maxlifo(", s, ", ", k, ")")

  # Special cases
  if k = 0 then return []
  if k = *s then return [s]

  Outp := []
  if k = 1 then {
    every put(Outp, !s)
    return Outp
  }

  # Default case
  S := set()
  K := []

  # Build cliques from output of maxlifo(s, k-1) with the remaining 
  # characters in s, substituting empty strings as placeholders for 
  # subsets already listed.
  every inps := !maxlifo(s, k-1) do { 
    R := []
    every ch := !s do
      if not find(ch, inps) then {
        cand := reorder(inps ++ ch, s)
        if member(S, cand) then cand := "" else insert(S, cand)
        put(R, cand)
      }
    put(K, R)
  }

  # Mark ‘first’ subset in each row with initial "!"
  every i := 1 to *K - 1 do {
    every j := 1 to *K[i] do
      if K[i, j] ~== "" & K[i+1, j] == "" then {
        K[i, j] := "!" || K[i, j]
        break
      }
  }

  # Remove rows containing only placeholders
  every i := *K to 1 by -1 do {
    every if !K[i] ~== "" then break next
    delete(K, i)  
  }

  # Mark ‘last’ subset in each row with final "!"
  every i := 1 to *K - 1 do 
    every j := 1 to *K[i] do 
      if K[i+1, j][1] == "!" then {
        K[i, j] ||:= "!"
        break
      }

  # Build output list
  every R := !K do {

    # Delete placeholders from row (no longer needed and in the way)
    every j := *R to 1 by -1 do if R[j] == "" then delete(R, j)

    # Handle ‘first’ subset and remove from row
    # N.B. ‘First’ subset will be leftmost or rightmost in row
    if R[1][1] == "!" then 
      put(Outp, trim(get(R), '!', 0)) 
      else put(Outp, trim(pull(R), '!', 0))   

    # Handle any remaining subsets, ‘last’ subset last, stripping '!' markers
    # N.B. ‘Last’ subset will be leftmost or rightmost in row after removal
    # of ‘first’ subset.
    if R[-1][-1] == "!" then while put(Outp, trim(get(R), '!', 0)) else
      while put(Outp, trim(pull(R), '!', 0))
  }

  return Outp

end


procedure reorder(cs:cset, s:string)
# Reorder cset cs according to string s

  local r
  # If no s, return set in alphabetical order
  if /s then return string(cs)

  r := ""
  s ? while tab(upto(cs)) do r ||:= move(1)
  return r

end
于 2014-03-23T02:54:56.280 に答える