這一個不應該太難,但我的頭腦似乎有一個堆棧溢出(huehue)。我有一系列的列表,我想查找它們可以排序的所有排列。所有的列表都有不同的長度。如何迭代不同長度的列表以查找所有排列?
例如:
列表1:1
列表2:1,2
所有排列將是:
1,1
1,2
在我的情況下,我不會切換數字。 (例如2,1) 寫這個最簡單的方法是什麼?
這一個不應該太難,但我的頭腦似乎有一個堆棧溢出(huehue)。我有一系列的列表,我想查找它們可以排序的所有排列。所有的列表都有不同的長度。如何迭代不同長度的列表以查找所有排列?
例如:
列表1:1
列表2:1,2
所有排列將是:
1,1
1,2
在我的情況下,我不會切換數字。 (例如2,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
嵌套循環(其中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;
}
}
}
感謝您的回答!這似乎是一個非常有效的解決方案。不過,我對於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
適用於無序組(系列)這很好.. –
這幾乎是正確的。但在我的情況下,我最終可能會得到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%
可能的重複[列出字符串/ 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 –