如何迭代不同长度的列表以查找所有排列？

这一个不应该太难，但我的头脑似乎有一个堆栈溢出（huehue）。我有一系列的列表，我想查找它们可以排序的所有排列。所有的列表都有不同的长度。如何迭代不同长度的列表以查找所有排列？

例如：

列表1：1

列表2：1，2

所有排列将是：

1,1

1,2

在我的情况下，我不会切换数字。（例如2,1）写这个最简单的方法是什么？

来源

2016-07-31 Emric Månsson

可能的重复[列出字符串/ inte的所有排列ger]（http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer） – 2016-07-31 07:54:45

你是什么意思的一系列名单？你的例子只显示两个。你只有两个还是你有更多？你是否在所有列表的笛卡尔积之后？ – Enigmativity

你的意思是排列？或者，也许你真的是指组合（又名笛卡尔产品）？两个列表ABC和12的组合将是A1，B1，C1，A2，B2，C2 –

如果下面是最简单的方法，但IMO它是最有效的方式，我不能说。它基本上是我的答案的一个通用版本的Looking at each combination in jagged array：

public static class Algorithms 
{ 
    public static IEnumerable<T[]> GenerateCombinations<T>(this IReadOnlyList<IReadOnlyList<T>> input) 
    { 
     var result = new T[input.Count]; 
     var indices = new int[input.Count]; 
     for (int pos = 0, index = 0; ;) 
     { 
      for (; pos < result.Length; pos++, index = 0) 
      { 
       indices[pos] = index; 
       result[pos] = input[pos][index]; 
      } 
      yield return result; 
      do 
      { 
       if (pos == 0) yield break; 
       index = indices[--pos] + 1; 
      } 
      while (index >= input[pos].Count); 
     } 
    } 
}

您可以看到链接的答案解释（不久它模拟嵌套循环）。此外，由于性能原因，它会产生内部缓冲区，无需克隆它，如果要将结果存储起来供以后处理，则需要克隆它。

示例用法：

var list1 = new List<int> { 1 }; 
var list2 = new List<int> { 1, 2 }; 
var lists = new[] { list1, list2 }; 

// Non caching usage 
foreach (var combination in lists.GenerateCombinations()) 
{ 
    // do something with the combination 
} 

// Caching usage 
var combinations = lists.GenerateCombinations().Select(c => c.ToList()).ToList();

UPDATE：的GenerateCombinations是一个标准的C＃iterator方法，和实现基本上模拟N嵌套循环（其中N是input.Count）这样的（在伪代码）：

对（INT I = 0;我 < input [0] .Count;我 ++）
对（INT I = 0;我 <输入[1] .Count之间;我 ++）
对（INT I = 0;我 <输入[2] .Count之间;我 ++）
...
对（INT I _N-1 = 0;我_N-1 <输入[N-1 ]。计数;我_N-1 ++）
收率{输入[0] [I ]，输入[1] [I ]，输入[2] [I ]，...，输入[N-1] [I _N-1]}

或表示它是不同的：

for (indices[0] = 0; indices[0] < input[0].Count; indices[0]++) 
{ 
    result[0] = input[0][indices[0]]; 
    for (indices[1] = 0; indices[1] < input[1].Count; indices[1]++) 
    { 
     result[1] = input[1][indices[1]]; 
     // ... 
     for (indices[N-1] = 0; indices[N-1] < input[N-1].Count; indices[N-1]++) 
     { 
      result[N-1] = input[N-1][indices[N-1]]; 
      yield return result; 
     } 
    } 
}

来源

2016-07-31 09:51:07

感谢您的回答！这似乎是一个非常有效的解决方案。不过，我对于for循环中的IEnumerables和可选值有点新鲜。我会在几个小时后回来，当我了解代码并提高您的答案时。：D –

不客气。我不知道你是否需要一个解决方案或理解如何实现它，所以我假设前者，否则可能会更多地集中在解释。 –

好的，我仍然不完全理解代码（也读过其他帖子的答案）。 ._。如果你觉得这样，我会非常感激解释发生了什么。我已经阅读了一些关于IEnumerables的内容，但仍然无法将其包围。 –

嵌套循环：

List<int> listA = (whatever), listB = (whatever); 
var answers = new List<Tuple<int,int>>; 
for(int a in listA) 
    for(int b in listB) 
     answers.add(Tuple.create(a,b)); 
// do whatever with answers

来源

2016-07-31 07:54:56 solarshado

适用于无序组（系列）这很好.. –

这几乎是正确的。但在我的情况下，我最终可能会得到40个不同长度的列表。我读过元组文档，你可以制作8个元组。最有可能的是，我可以很容易地从a和b整合一个列表，但我不知道我将如何制作〜40个嵌套for循环？有递归解决方案吗？ –

尝试这种情况：

Func<IEnumerable<string>, IEnumerable<string>> combine = null; 
combine = xs => 
    xs.Skip(1).Any() 
    ? xs.First().SelectMany(x => combine(xs.Skip(1)), (x, y) => String.Format("{0}{1}", x, y)) 
    : xs.First().Select(x => x.ToString()); 

var strings = new [] { "AB", "12", "$%" }; 

foreach (var x in combine(strings)) 
{ 
    Console.WriteLine(x); 
}

这给了我：

 
A1$ 
A1% 
A2$ 
A2% 
B1$ 
B1% 
B2$ 
B2%

来源

2016-07-31 10:59:08 Enigmativity

如何迭代不同长度的列表以查找所有排列？

回答

相关问题