algorithm - 使用堆栈打印给定 N 轮 RPS 的所有可能结果排列

Question

给定 n 轮，使用堆栈作为主要策略打印所有可能的剪刀石头布排列。

我曾经知道如何做到这一点，但在有一段时间没有练习堆栈后，我感到很困惑。

有人可以提供有关如何填充堆栈的有用提示吗？

我知道 n 个输入有 3^n 个输出。

对于 n = 1，预期答案是 3。可能的解决方案是:

def rps(n)
  stack = []
  answer = []

  if n > 0
    stack.push([r,p,s])
    n -= 1

  while !stack.isEmpty()
    array = stack.pop();

    forEach elem in array
      // I still can't figure out where to go from here!!

我知道在递归解决方案中，对于 n=1，它会变成 r,p,s

对于 n=2，答案会附加 rr、rp、rs、pr、pp、ps、sr、sp、ss

对于 n=3，它将是 rrr、rrp、rrs、rpr 等...

Answer 1

根据我的理解，我们可以从空堆栈开始，对于弹出堆栈的每个排列，我们将所有可能性附加到排列，然后将其添加回堆栈。

Stack s = new Stack();
s.add("");
ArrayList<String> result;
while(!s.isEmpty()){
    String v = s.pop();
    if(v.length() == n){//All n rounds finished, add to final result
       result.add(v);
       continue;
    }
    //Now, add the result of this round to the current permutation.

    s.push(v + "r");
    s.push(v + "s");
    s.push(v + "p");

}
return result;