在我的回答中,我会忽略你上一次得到的结果:Adam,Bob:1、2、3
,因为从逻辑上讲它是一个例外。跳到最后看看我的输出。
说明:
想法是迭代“每个元素属于哪个组”的组合。
假设您有元素“a,b,c”,并且您有组“1,2”,让我们拥有一个大小为3的数组作为元素数量,其中包含所有可能的组合“1,2”,WITH重复:
{1, 1, 1} {1, 1, 2} {1, 2, 1} {1, 2, 2}
{2, 1, 1} {2, 1, 2} {2, 2, 1} {2, 2, 2}
现在我们将对每个组进行处理,并将其转换为键值集合,具体逻辑如下:
elements[i]
组将成为
comb[i]
的值。
Example with {1, 2, 1}:
a: group 1
b: group 2
c: group 1
And in a different view, the way you wanted it:
group 1: a, c
group 2: b
经过所有这些步骤,您只需要过滤掉不包含所有组合的组合,因为您希望所有组都至少有一个值。
因此,您应该检查所有组是否出现在某个组合中,并过滤不匹配的组合,这样您就会得到:
{1, 1, 2} {1, 2, 1} {1, 2, 2}
{2, 1, 2} {2, 2, 1} {2, 1, 1}
这将导致:
1: a, b
2: c
1: a, c
2: b
1: a
2: b, c
1: b
2: a, c
1: c
2: a, b
1: b, c
2: a
这种组合逻辑的破解方法可以适用于更多的元素和组。以下是我的实现方式,可能还有更好的方法,因为在编码时我也有点迷失(这确实不是一个直观的问题呵呵),但它运行良好。
实现:
public static IEnumerable<ILookup<TValue, TKey>> Group<TKey, TValue>
(List<TValue> keys,
List<TKey> values,
bool allowEmptyGroups = false)
{
var indices = new int[values.Count];
var maxIndex = values.Count - 1;
var nextIndex = maxIndex;
indices[maxIndex] = -1;
while (nextIndex >= 0)
{
indices[nextIndex]++;
if (indices[nextIndex] == keys.Count)
{
indices[nextIndex] = 0;
nextIndex--;
continue;
}
nextIndex = maxIndex;
if (!allowEmptyGroups && indices.Distinct().Count() != keys.Count)
{
continue;
}
yield return indices.Select((keyIndex, valueIndex) =>
new
{
Key = keys[keyIndex],
Value = values[valueIndex]
})
.OrderBy(x => x.Key)
.ToLookup(x => x.Key, x => x.Value);
}
}
使用方法:
var employees = new List<string>() { "Adam", "Bob"};
var jobs = new List<string>() { "1", "2", "3"};
var c = 0;
foreach (var group in CombinationsEx.Group(employees, jobs))
{
foreach (var sub in group)
{
Console.WriteLine(sub.Key + ": " + string.Join(", ", sub));
}
c++;
Console.WriteLine();
}
Console.WriteLine(c + " combinations.");
输出:
Adam: 1, 2
Bob: 3
Adam: 1, 3
Bob: 2
Adam: 1
Bob: 2, 3
Adam: 2, 3
Bob: 1
Adam: 2
Bob: 1, 3
Adam: 3
Bob: 1, 2
6 combinations.
更新
组合键组合原型:
public static IEnumerable<ILookup<TKey[], TValue>> GroupCombined<TKey, TValue>
(List<TKey> keys,
List<TValue> values)
{
for (var i = 1; i <= keys.Count; i++)
{
foreach (var lookup in Group(Enumerable.Range(0, i).ToList(), keys))
{
foreach (var lookup1 in
Group(lookup.Select(keysComb => keysComb.ToArray()).ToList(),
values))
{
yield return lookup1;
}
}
}
}
还存在一些重复的问题,但它可以生成所有结果。
以下是我会使用的临时解决方案,用于去除重复项:
var c = 0;
var d = 0;
var employees = new List<string> { "Adam", "Bob", "James" };
var jobs = new List<string> {"1", "2"};
var prevStrs = new List<string>();
foreach (var group in CombinationsEx.GroupCombined(employees, jobs))
{
var currStr = string.Join(Environment.NewLine,
group.Select(sub =>
string.Format("{0}: {1}",
string.Join(", ", sub.Key),
string.Join(", ", sub))));
if (prevStrs.Contains(currStr))
{
d++;
continue;
}
prevStrs.Add(currStr);
Console.WriteLine(currStr);
Console.WriteLine();
c++;
}
Console.WriteLine(c + " combinations.");
Console.WriteLine(d + " duplicates.");
输出:
Adam, Bob, James: 1, 2
Adam, Bob: 1
James: 2
James: 1
Adam, Bob: 2
Adam, James: 1
Bob: 2
Bob: 1
Adam, James: 2
Adam: 1
Bob, James: 2
Bob, James: 1
Adam: 2
7 combinations.
6 duplicates.
请注意,它也会生成非组合的组(如果可能-因为不允许空组)。要仅生成组合键,您需要替换此内容:
for (var i = 1
通过这个:
for (var i = 1
在GroupCombined方法的开头,使用三个员工和三个职位测试该方法,以了解其确切工作方式。
另一个编辑:
更好的重复处理是在GroupCombined级别处理重复的键组合:
public static IEnumerable<ILookup<TKey[], TValue>> GroupCombined<TKey, TValue>
(List<TKey> keys,
List<TValue> values)
{
for (var i = 1; i <= keys.Count; i++)
{
var prevs = new List<TKey[][]>();
foreach (var lookup in Group(Enumerable.Range(0, i).ToList(), keys))
{
var found = false;
var curr = lookup.Select(sub => sub.OrderBy(k => k).ToArray())
.OrderBy(arr => arr.FirstOrDefault()).ToArray();
foreach (var prev in prevs.Where(prev => prev.Length == curr.Length))
{
var isDuplicate = true;
for (var x = 0; x < prev.Length; x++)
{
var currSub = curr[x];
var prevSub = prev[x];
if (currSub.Length != prevSub.Length ||
!currSub.SequenceEqual(prevSub))
{
isDuplicate = false;
break;
}
}
if (isDuplicate)
{
found = true;
break;
}
}
if (found)
{
continue;
}
prevs.Add(curr);
foreach (var group in
Group(lookup.Select(keysComb => keysComb.ToArray()).ToList(),
values))
{
yield return group;
}
}
}
}
看起来,最好在方法中添加约束条件,以便TKey
将是ICompareable<TKey>
,也可能是IEquatable<TKey>
。
这最终会得到0个重复项。
Adam : 2; Bob: 1, 3
和Adam : 3; Bob: 1, 2
? - Douglas