2016-07-31 86 views
0

這一個不應該太難,但我的頭腦似乎有一個堆棧溢出(huehue)。我有一系列的列表,我想查找它們可以排序的所有排列。所有的列表都有不同的長度。如何迭代不同長度的列表以查找所有排列?

例如:

列表1:1

列表2:1,2

所有排列將是:

1,1

1,2

在我的情況下,我不會切換數字。 (例如2,1) 寫這個最簡單的方法是什麼?

+1

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

+0

你是什麼意思的一系列名單?你的例子只顯示兩個。你只有兩個還是你有更多?你是否在所有列表的笛卡爾積之後? – Enigmativity

+0

你的意思是排列?或者,也許你真的是指組合(又名笛卡爾產品)?兩個列表ABC和12的組合將是A1,B1,C1,A2,B2,C2 –

回答

1

如果下面是最簡單的方法,但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嵌套循環(其中Ninput.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; 
     } 
    } 
} 
+0

感謝您的回答!這似乎是一個非常有效的解決方案。不過,我對於for循環中的IEnumerables和可選值有點新鮮。我會在幾個小時後回來,當我瞭解代碼並提高您的答案時。 :D –

+0

不客氣。我不知道你是否需要一個解決方案或理解如何實現它,所以我假設前者,否則可能會更多地集中在解釋。 –

+0

好的,我仍然不完全理解代碼(也讀過其他帖子的答案)。 ._。如果你覺得這樣,我會非常感激解釋發生了什麼。我已經閱讀了一些關於IEnumerables的內容,但仍然無法將其包圍。 –

0

嵌套循環:

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 
+0

適用於無序組(系列)這很好.. –

+0

這幾乎是正確的。但在我的情況下,我最終可能會得到40個不同長度的列表。我讀過元組文檔,你可以製作8個元組。最有可能的是,我可以很容易地從a和b整合一個列表,但我不知道我將如何製作〜40個嵌套for循環?有遞歸解決方案嗎? –

0

嘗試這種情況:

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% 
相關問題