0

我正在查找如何执行字符串排列并找到下面的解决方案。但是我很难理解所使用的逻辑。尤其是这一行。for(final String permutation : Permuatations(subList(head,words)))据我所知，作者是在其自身“Permutations”上调用一个函数来执行其中的 subList 函数，这很难让我理解。谁能让我更清楚一点？任何指导将不胜感激。

public static void main (String [] args)
    {
        for(final String s: Permuatations(Arrays.asList("This ","is ","String ")))
                {
            System.out.println("6. THE FINAL OUTPUT " +s);
                }
    }

    public static List<String> Permuatations(final List<String> words)
    {
        final List<String> perms = new ArrayList<String>();
        if (words.size() == 1)
        {
             perms.add(words.get(0));
             System.out.println("3. permuatations if words " + words);
             System.out.println("4. PERMS LIST " + perms);
        }

        else
        {
            for(final String head : words)
            {
                for(final String permutation : Permuatations(subList(head,words)))
                {
                    perms.add(head + permutation);
                    System.out.println("5 .SubList HEAD " + head + " PERMUATATION " + permutation  + " Word Size " + words.size() );
                }
            }
        }
        return perms;
    }


public static List<String> subList(final String elementToRemove, final List<String> elements)
{
    final List<String> subList = new ArrayList<String>();
    for(final String s : elements)
    {
        //System.out.println(" 1. STRING s " + s + " ELEMENTS " + elements);
        if(!s.equals(elementToRemove))
        {
            System.out.println(" 1. STRING S " + s + " ELEMENTS " + elements);
            subList.add(s);
            System.out.println("2 STRING S " + s + " TO SUBLIST " + subList);
        }


    }

    return subList;
}
4

3 回答 3

2

这正是他们正在做的事情。它被称为递归，一开始很难理解。想象一下你有字符串：

A B C D

实际上，您所做的就是依次选择每个字符串，然后找到剩余字符串的所有排列，并预先添加您选择的字符串。

Choose A, get all permutations of {B,C,D} and append A. 
Choose B, get all permutations of {A,C,D} and append B. 
Choose C, get all permutations of {A,B,D} and append C. 
Choose D, get all permutations of {A,B,C} and append D.

现在，我们的子问题看起来非常相似，但更小。这就是递归的核心。拿一个问题，想办法把它变成一个更小的问题。现在，继续把它变成一个小问题，直到它变得微不足道。现在我们必须弄清楚如何生成 3 个字符串的排列。

Permute(A B C) 
Choose A, get all permutations of {B,C} and append A.
Choose B, get all permutations of {A,C} and append B.
Choose C, get all permutations of {A,B} and append C.

结构相同，但问题更小。所以更进一步。我们如何进行置换(AB)

Permute(A B) 
Choose A, get all permutations of {B} and append A.
Choose B, get all permutations of {A} and append B.

所以现在我们只需要置换一个字符串。那是微不足道的。

Permute(A)
A

所以现在我们有一种方法来置换大小为 1 的字符串列表，并且我们已经定义了如何通过置换大小为 N-1 的列表来置换大小为 N 的列表。因此，我们可以置换任何大小 >= 1 的列表，方法是用稍微小一点的问题版本来称呼我们自己。这就是递归的美妙之处。您只需定义如何解决最小的问题，以及如何使用该解决方案来构建更大的解决方案，并且它建立在自身之上。

于 2013-03-23T15:35:11.790 回答
0

This is a recursive algorithm, it essentially takes each element in the array as the first one then adds to to it the output of calling itself without that element.

Take 3 elements A, B and C and walk through the logic, lets call our function perm.

so, we want

perm({A, B, C})

this equals

A + perm({B, C})
B + perm({A, C})
C + perm({A, B})

expand again

A + B + perm({C})
A + C + perm({B})
B + A + perm({C})
B + C + perm({A})
C + A + perm({B})
C + B + perm({A})

as perm({X}) = X we end up with

A + B + C
A + C + B
B + A + C
B + C + A
C + A + B
C + B + A
于 2013-03-23T15:43:49.607 回答
0

The scheme used is "divide and conquer". It's basic idea is to break up a big problem into a set of smaller problems to which the same mechanism is applied until an "atomic" level of the problem is reached. In other words: A problem of size n is broken up into n problems of size n-1 continuously. At the bottom there is a simple way of dealing with the problem of size 1 (or any other constant). This is usually done using recursion (as Calgar99) pointed out already.

A very nice example of that scheme that will also twist you head a bit are the "Towers of Hanoi". Check it out and the ingenuity of such an approach will hit you.

As for the presented code: The permutation of n words is the concatenation of the permutation of n-1 words with each of the n original words. This recursive definition represents a quite elegant solution for the problem.

于 2013-03-23T15:44:36.327 回答