0

我有这段代码递归地获取一组字符串的所有排列：

public static 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> combos : combinations(subStrings))
            {
                combos.add(str);
                result.add(combos);
            }
        }

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

如果我的 arraylist 包含太多值，它会溢出堆栈。从那以后，我了解到将算法从递归转换为迭代将帮助我解决这个内存问题，因为我将自己在堆上处理堆栈，而不是使用本机堆栈。我以前从未这样做过，也无法解决如何解决这个问题。我的问题并不像看到的这种转换的例子那么简单，所以我将非常感谢一些关于我如何实现这一点的提示。

4

2 回答 2

1

你基本上需要的是一个迭代的 powerset 构造。查看此示例代码（“迭代”部分）以了解如何在 Java 中完成集合任务。如果在组合原始字符串的给定子集时需要区分不同的顺序，则必须在第二个处理步骤中生成每个 powerset 元素的所有排列。这个页面将让您开始了解如何实现它（使用代码为您提供索引的所有排列1..<list_size>，添加一个简单的映射来获取有序的字符串列表）。

但是请考虑您是否真的需要字符串集的显式表示。您可以等效地将所取的数字k用作1..<original set size>位向量，其中位 #i指示是否i包含源列表中位置的字符串。在有序组合的情况下，排列将k由其1位数唯一确定。

由于排列是可排序的，您实际上只需要 2 个数字 + 原始列表来唯一标识结果的每个元素并轻松重建实际的字符串组合。

您可能也对这个 SO question感兴趣。

于 2013-06-12T10:36:05.337 回答
1

像下面这样的东西怎么样，它使用一个特殊的 WorkPair 类来模拟将在递归方法中创建的堆栈帧。通常，当转换为迭代方法时，您可能需要创建一个存储部分工作的数据结构，因为在递归方法中，此信息存储在堆栈中（我们没有）。

private static class WorkPair{

  public final List<String> so_far;
  public final List<String> left;
  public WorkPair(List<String> sf,List<String> l){
    so_far=sf;left=l;
  }

}

public static List<List<String>> combinationsIterative(List<String> strings)
{

    Queue<WorkPair> queue = new LinkedList<WorkPair>();

        // setup queue
        for(String str : strings){
           List<String> so_far = new ArrayList<String>(Arrays.asList(str));
           List<String> left = new ArrayList<String>(strings);
           left.remove(str);
           queue.add(new WorkPair(so_far,left));
        }

        // collect the results
        List<List<String>> result = new ArrayList<List<String>>();            
        while(!queue.isEmpty()){
          WorkPair pair = queue.remove();
          // at each stage add the list so_far
          List<String> so_far_add = new ArrayList<String>(pair.so_far);
          result.add(so_far_add);

          // if there's more work to be done create more workpairs
          if(pair.left.size()>0){
            // push work items for so_far + one element of left
            for(String str : pair.left){
                   List<String> so_far = new ArrayList<String>(pair.so_far);
                   so_far.add(str);
                   List<String> left = new ArrayList<String>(pair.left);
                   left.remove(str);
                   queue.add(new WorkPair(so_far,left));      
            }
          }

        }

    return result;
}
于 2013-06-12T10:24:45.903 回答