java - 了解此算法以查找字符串的排列(递归)

Question

我正在翻阅我的教科书，但我无法真正理解这是如何递归地生成字符串的排列

class PermutationIterator
{
    private String wrd;
    private int current;
    private PermutationIterator Iter;
    private String tl;
    // Constructor
    public PermutationIterator(String s)
    {
        wrd = s;
        current = 0;
        if (wrd.length() > 0)
            Iter = new PermutationIterator(wrd.substring(1));
    }

    public String nextPermutation()
    {
        if(wrd.length() == 0)
        {
            current++;
            return "";
        }

        char c = wrd.charAt(current);
        String nextPermut = Iter.nextPermutation();
        if(!Iter.hasMorePermutations())
        {
            System.out.println("Current value is " + current + " word length is " + wrd.length());
            current++;
            if (current >= wrd.length()) {
                Iter = null;
            }
            else
            {
                if (current + 1 >= wrd.length())
                    tl = wrd.substring(0,current);
                else
                    //System.out.println("Reached");
                    tl = wrd.substring(0,current) + wrd.substring(current + 1, wrd.length());
                    Iter = new PermutationIterator(tl);
            }
        }
        return c + nextPermut;
    }

    public boolean hasMorePermutations()
    {
        System.out.println("Inside this method we have current= " + current + " with wrdlength "  + wrd.length() +"with the word " + wrd);
        return current < wrd.length();
    }
}

这被调用

public static void main(String [] args)
    {
        PermutationIterator iter = new PermutationIterator("eat");
        while(iter.hasMorePermutations())
        {
            System.out.println(iter.nextPermutation());
        }
    }

对于 eat这将输出
eat
eta
aet
ate
tea
tae


我的尝试

在过去的三天里，在试图理解一切之前，我一直在努力弄清楚 !Iter.hasMorePermutations() 到底是怎么回事。到达了。这可能是错误的唯一方法是如果 return current < wrd.length();不是真的。即wrd.length() <= current .

现在我真的开始迷失了。我尝试在 !Iter.hasMorePermutations() 中打印出 word.length 和 current 的值分支只是为了看看发生了什么。

Current value is 0 word length is 1
Current value is 0 word length is 2
eat

等等……这怎么可能？我们到达这个分支的条件不是当前值大于我们的字长吗？我们是怎么到达这个分支的？

我还附上了一张我试图追踪程序的照片，

感谢阅读本文!

Answer 1

对于每个字长，一次有四个迭代器处于 Activity 状态。它们都有自己的 current 值，对 hasMorePermutations 的调用正在检查 current 和 length 的值在下一个迭代器上，而不是它本身。所以你可能想要输出:

System.out.println("Current value is " + Iter.current + " word length is " + Iter.wrd.length());

首先，它们所有的当前值都是 0，所以我们有 'eat':

(word = 'eat', current = 0, length = 3)
 (word = 'at', current = 0, length = 2)
  (word = 't', current = 0, length = 1)
   (word = '', current = 0, length = 0)

每个迭代器在下一个调用 nextPermutation，直到我们到达最后一个迭代器，它的 current 值递增，因为 wrd.length() == 0 。所以我们得到:

(word = 'eat', current = 0, length = 3)
 (word = 'at', current = 0, length = 2)
  (word = 't', current = 0, length = 1)
   (word = '', current = 1, length = 0)

这是在第三个迭代器的 Iter.hasMorePermutations() 中检测到的，然后它将增加自己的 current 值并重置最后一个迭代器:

(word = 'eat', current = 0, length = 3)
 (word = 'at', current = 0, length = 2)
  (word = 't', current = 1, length = 1)
   (word = '', current = 0, length = 0)

这由第二个迭代器类似地检测到，它重置最后两个迭代器:

(word = 'eat', current = 0, length = 3)
 (word = 'at', current = 1, length = 2)
  (word = 'a', current = 0, length = 1)
   (word = '', current = 0, length = 0)

第一个迭代器对 Iter.hasMorePermutations() 的调用将返回 false，因此它不会增加其当前值，并给出下一个字符串“eta”。