3

ここには 2 つのスタックがあります。

A: 1,2,3,4 <- Stack Top
B: 5,6,7,8

A と B は、他の 2 つのスタック (C と D) に飛び出します。

Example: 
 pop(A),push(C),pop(B),push(D).
 If an item have been popped out , it must be pushed to C or D immediately.

では、 C と D のすべての可能性を見つけるアルゴリズムはありますか?

どうもありがとう ！

4

3 に答える 3

0

私はアイデアを得ましたが、それが正しいかどうかわかりません:

8 ビットのスタックをセットアップします。1 は A ポップを意味し、0 は B ポップを意味します (4 つの 1 と 4 つの 0 があることを確認してください)。

したがって、答えは、8 ビット配列の組み合わせのすべての可能性を見つけることになります。

そして、8 ビットを繰り返して A または B を取り出します。

コードは次のとおりです。

public class Test {
public static void generate(int l, int[] a) {
    if (l == 8) {
        if (isValid(a)) {
            for (int i = 0; i < l; i++) {
                System.out.print(a[i]);
            }
            System.out.println();
        }
    } else {
        for (int i = 0; i < 2; i++) {
            a[l] = i;
            generate(++l, a);
            --l;
        }
    }
}

// the combination must have four 0 and four 1.
public static boolean isValid(int[] a) {
    int count = 0;
    for (int i = 0; i < a.length; i++) {
        if (a[i] == 0) count++;
    }
    if (count != 4) return false;
    return true;
}

public static void main(String[] args) {
    generate(0, new int[8]);
}

}

于 2012-06-04T04:30:36.167 に答える
0

C と D の内容は、4 つの A と 4 つの B のシーケンスとして任意の順序で書き出すことができます。

AABABBBA (A を 2 回、次に B を 1 回、次に A を 1 回というようにポップすることを表します)

そのようなシーケンスは、正確に8 から 4 つ選択されます。したがって、そのようなすべてのシーケンス （「繰り返しのない組み合わせ」）を繰り返して、答えを取得してください。

于 2012-06-04T18:01:25.473 に答える
0

スタックのすべての可能な pop のリストを生成してから、シミュレートできます。

ただし、重複が発生する可能性があります。各スタックに要素が 2 つしかない場合を考えてみてください。a が c にプッシュされ、b が d にプッシュされる場合、それらがプッシュされる順序は関係ありません。

def simulate(steps):
    source={'a':range(4),'b':range(4,8)}
    res = {'c':"",'d':""}; 
    for i,step in enumerate(steps):
        res[step[1]]+=str(source[step[0]].pop())
    # this is what each stack will look like
    return res['c']+'-'+res['d']  

def steps(a_left,b_left):
    ret = []
    if a_left>0:
        substeps = steps(a_left-1,b_left)
        ret.extend( [ x + [('a','c')] for x in substeps] )
        ret.extend( [ x + [('a','d')] for x in substeps] )
    if b_left>0:
        substeps = steps(a_left,b_left-1)
        ret.extend(  [ x + [('b','c')] for x in substeps] )
        ret.extend(  [ x + [('b','d')] for x in substeps] )
    if(len(ret)==0):
        return [[]]
    return ret;

そして結果：

>>> [x for x in steps(1,1)]
[[('b', 'c'), ('a', 'c')], [('b', 'd'), ('a', 'c')], [('b', 'c'), ('a', 'd')], [
('b', 'd'), ('a', 'd')], [('a', 'c'), ('b', 'c')], [('a', 'd'), ('b', 'c')], [('
a', 'c'), ('b', 'd')], [('a', 'd'), ('b', 'd')]]
>>> [simulate(x) for x in steps(1,1)]
['73-', '3-7', '7-3', '-73', '37-', '7-3', '3-7', '-37']
>>> len(set([simulate(x) for x in steps(4,4)]))
5136

ターゲット スタックが 1 つだけの 2 つのスタックを考えると、一意のスタックの数は (2*n)!/(n!)^2 でわかります。これは、「A」が 4 個、「B」が 4 個の 8 個の要素の順列の数と同じです。次に、それらをサブセットに分割することで、それらを個々のスタックに割り当てることができます。スタックごとに N 個の一意の番号を持つサブセットの数は 2^(2^n) になります。

(2^(2*n))/((2*n)!/(n!)^2)

ただし、これらをより効率的に生成する方法はわかりません。

于 2012-06-04T03:25:01.230 に答える