如何使这种组合/置换方法递归？ [英] How do I make this combinations/permutations method recursive?

问题描述

我有一个Strings的arraylist想要将所有可能的组合存储到另一个集合中。

I have an arraylist of Strings that want to have all possible combinations stored into another collection.

例如：

[air,bus,car]
->
[air]
[bus]
[car]
[air,bus]
[air,car]
[bus,air]
[bus,car]
[car,air]
[car,bus]
[air,bus,car]
[air,car,bus]
...
[car,bus,air]

重复并不重要。我现在的代码是：

Repetitions are not important. The code right now I have is:

public ArrayList<String> comb(ArrayList<String> wrds, ArrayList<String> str, int size)
{
    ArrayList<String> s = new ArrayList<String>();
    s.addAll(str);
    if(size != a1.size())
    {
        Iterator e = a1.iterator();
        while(e.hasNext())
        {
            s.add((String)e.next());
        }
        size++;
    }
}

我试图让它以递归方式调用自己它可以存储组合。我可以获得关于我的代码中缺少哪个或哪个部分的任何帮助吗？

I am trying to get it to recursively call itself so it can store the combinations. Can I get any help as to where or which part I am missing in my code?

推荐答案

看到这是作业，我我会试着给你答案的背景。

Seeing as this is homework, I'll try to give you background to the answer.

解决这个问题的关键是使用递归。

The key to solving this is to use recursion.

首先想象一下你的数组中有两个项目。您可以删除第一个项目，为您提供第一个组合。将剩余项目添加到第一个项目将为您提供第二个组合。删除第二个项目为您提供第三个组合。添加剩余项目将为您提供第四种组合。如果你有 [air，bus] 它就像是：

First imagine you have two items in your array. You'd could remove the first item to give you your first combination. Adding the remaining item to the first item gives you the second combination. Removing the second item give you the third combination. Adding the remaining item gives you the forth combination. If you had ["air", "bus"] it'd be something like:

["air"]
["air", "bus"]
["bus"]
["bus", "air"]

返回的方法可能如下所示：

A method that returns that might look like:

String[][] combinations(String[] strings)

需要注意的重要事项是，包含单个字符串的数组可以传递给此方法，并且它可以返回包含其中包含单个字符串的数组的数组。

The important things to note are the an array containing a single string can be passed to this method and it can return an array containing an array with a single string in it.

问题很复杂，因为你必须保持字符串组合的计数，所以在我们解决这个问题之前，理解递归是很重要的。

The problem is complicated a little because you have to keep a tally of the string combinations, so before we get to solving that, it's important that you understand recursion.

想象一下，你想要编写一个乘法方法，它取两个数并乘以它们，但你只能使用加法和减法。您可以编写一个递归函数，将其中一个数字添加到自身，直到另一个数字达到退出条件，如：

Imagine you wanted to write a multiplication method that takes two numbers and multiplies them but you only have addition and subtraction at your disposal. You could write a recursive function that adds one of the numbers to itself until the other number reaches an exit condition, something like:

public int multiply(int value1, int value2) 
{
  if (value1 > 1) 
  {
    int remaining = value1 - 1;
    return value2 + multiply(remaining, value2);
  }
  else 
  {
    return value2;
  }
}

你可以用一个数组做同样的事情，只有在a值命中 1 时才退出，当数组包含一个项目时退出，如：

You can do just the same thing with an array, only instead to exiting when the a value hit's 1 you exit when the array contains one item, something like:

public String[][] combinations(String[] strings) 
{
  if (strings.length > 1) 
  {
    ...
  }
  else 
  {
    return new String[][]{strings};
  }
}

出于Java API的原因，它更容易使用 java.util.List 而不是数组，所以你需要这样的东西：

For reasons with the Java API it's much easier to use java.util.List rather than arrays so you want something like:

public List<List<String>> combinations(List<String> strings) 
{
  if (strings.size()> 1) 
  {
    ...
  }
  else 
  {
    List<List<String>> result = new ArrayList<List<String>>();
    result.add(strings);
    return result;
  }
}

现在是 .. 。这是重要的一点。您需要保留一个列表列表作为结果，并迭代字符串。对于每个字符串，您可以将该字符串添加到结果中，然后您需要创建一个减去当前字符串的子列表，用于调用组合方法再次迭代结果，添加当前字符串包含的每个列表。在代码中，它看起来像：

Now it's the ... that's the important bit. You need to keep an list-of-lists that will be the result and iterate over the strings. For each of the strings you can add that string to the results and then you need create a sub-list that is minus the current string, which you use to call the combinations method again iterating over the result adding the current string each list it contains. In code it looks something like:

public List<List<String>> combinations(List<String> strings) 
{
  if (strings.size() > 1) 
  {
    List<List<String>> result = new ArrayList<List<String>>();

    for (String str : strings) 
    {
      List<String> subStrings = new ArrayList<String>(strings);
      subStrings.remove(str);

      result.add(new ArrayList<String>(Arrays.asList(str)));

      for (List<String> combinations : combinations(subStrings)) 
      {
        combinations.add(str);
        result.add(combinations);
      }
    }

    return result;
  }
  else 
  {
    List<List<String>> result = new ArrayList<List<String>>();
    result.add(new ArrayList<String>(strings));
    return result;
  }
}

总之，你正在做的是减少将字符串列表下移到单个项目，然后将其与前面的项目组合，以在线程返回调用堆栈时生成所有可能的组合。

In summary, what you're doing is reducing the list of strings down to a single item, then combining it with the preceeding items to produce all the possible combinations as the thread returns up the call stack.

这篇关于如何使这种组合/置换方法递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！