3

这里有两个堆栈：

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

A 和 B 将弹出到另外两个堆栈：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 pop，0 表示 B pop（只要确保有四个 1 和四个 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

您可以生成所有可能的堆栈弹出列表，然后模拟：

但是，会有重复，考虑每个堆栈上只有两个元素的情况。如果将 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

如果我们考虑只有一个目标堆栈的两个堆栈，我们可以在 (2*n)!/(n!)^2 处找到唯一堆栈的数量。这与 8 个元素的排列数相同，其中 4 个是“A”，其中 4 个是“B”。然后，我们可以通过将它们划分为子集来将它们分配给每个单独的堆栈 - 每个堆栈具有 N 个唯一编号的子集的数量将是 2^(2^n)

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

不过，我没有看到更有效地生成这些的方法。

于 2012-06-04T03:25:01.230 回答
0

C 和 D 的内容可以以任意顺序写成四个 A 和四个 B 的序列。

AABABBBA （代表弹出 A 两次，然后 B 一次，然后 A 一次，等等）

恰好有8 个选择 4 个这样的序列。因此，只需遍历每个这样的序列 （“无重复组合”）即可获得答案。

于 2012-06-04T18:01:25.473 回答