2017-08-25 33 views
0

我有一个对象列表,这些对象的数量是动态的。我需要找到这些对象的所有可能的组合。查找所有可能的组合,并重新选择允许的项目

我目前在这里我采取的对象列表的阶段,使用下面的代码没有repitition返回所有可能的组合:

static void Main(string[] args) 
    { 
     //Say, inputList contains randomObject1,randomObject2 and randomObject3 
     List<List<RandomObject>> AllCombos = ItemCombinations(inputList); 

    } 

    //maxComboCount denotes the maximum number of elements that can be in the combination 
    public static List<List<T>> ItemCombinations<T>(List<T> inputList, int maxComboCount) 
    { 

     int nonEmptyCombinations = (int)Math.Pow(2, inputList.Count) - 1; 

     List<List<T>> listOfCombinations = new List<List<T>>(); 


     for (int i = 1; i <= nonEmptyCombinations; i++) 
     { 
      List<T> thisCombination = new List<T>(); 
      for (int j = 0; j < inputList.Count; j++) 
      { 
       if ((i >> j) % 2 != 0) 
       { 
        thisCombination.Add(inputList[j]); 
       } 
      } 

      if (thisCombination.Count <= maxComboCount) 
      { 
       listOfCombinations.Add(thisCombination); 
      } 
     }      
     return listOfCombinations; 
    } 

我如何获得所有其他组合,在那里重复项目,maxComboCount将永远在那里,否则我所需的场景可能会陷入无限循环(如果我错了,请纠正我)。

例如, InputList:{r1,r2,r3}

当前阶段:{r1},{r2},{r3},{r1,r2},{r2,r3},{r3,r1},{r1,r2 ,r3}

通缉阶段(给定maxComboCount约束= 4):{r1},{r2},{r3},{r1,r1},{r1,r2},{r1,r3},{r2, {r2,r3},{r1,r1,r1},{r1,r1,r2},{r1,r1,r3}等等。 。

有一件事我试过了,

我重复,直到maxBaseCardCount并在每次迭代到另一个tempList加入inputList,我再传给这个tempList为满足在ItemCombinations参数HOD。

 //The loop will be constrained by the maximum number of objects allowed 
     for (int i = 0; i < maxComboCount; i++) 
     { 
      tempList.AddRange(inputList); 
     } 

     List<List<RandomObject>> AllCombos = ItemCombinations(tempList); 

这应该是一个快速和肮脏的解决办法,并确实给我需要的输出(有很多重复的值),但我不是很肯定它多少可以打破之前举行。因此,任何比我的方法更可靠的方法将非常感谢。

编辑

我加入问题的解释,请让我知道是否有任何其他的简化要求

InputList:这是一个对象的列表,从中可以组合成由

ItemCombinations:该函数返回从给定列表中的所有组合,而无需repitition(不是我想要的)

对于inputList = {1,2},ItemCombination返回:空,{1},{2},{1,2},即从长度为n的任何给定的列表中查阅

所有2^N唯一组合,我希望能够将这些项目与允许的重复项以及动态组合的长度结合起来。

实施例:

例如InputList:{r1,r2,r3}

ItemCombination函数最初返回:{r1},{r2},{r3},{r1,r2},{r2,r3},{r3,r1},{r1 ,R2,R3}

现在,我要的是,可以作出,如果有多少次没有限制每个对象可用于

我想要什么(给出maxComboCount约束的所有组合= 4):{r1},{r2},{r3},{r1,r1},{r1,r2},{r1,r3},{r2,r2},{r2,r3},{r3,r3} {r1,r1,r1},{r1,r1,r2},{r1,r1,r3},{r1,r2,r3}等等......

maxComboCount约束确保no列表大小> 4返回

基本上,我想从n个对象,其中k的范围可以从1到x(任何数量)

+0

你是指“没有重复的可能组合”是什么意思?你是指排列还是别的什么? – Arjang

+1

你能用简单的英文写出你想要的东西吗?我不想检查您的代码,以了解您想要实现的目标。 –

+0

“我需要的场景可能会陷入无限循环”这意味着你做错了什么,因为有或没有重复的元素,组合的数量如果总是有限的(尽管它可以变得非常快)。 – oerkelens

回答

1

你想找到拟定从m项的组合选择的k个对象的组合n重复项目池。订单在物品组中无关紧要,因此{1, 2, 2}{2, 2, 1}是等效的;只能添加其中的一个。 (理想情况下,这是项目按升序排列的项目。)

假设您有三个项目的池,并且想创建最多两个项目的集合。添加空集给你的结果:从

{} + {1} = {1} 
{} + {2} = {2} 
{} + {3} = {3} 

现在创建的两个项目组:

{} 

与任何项目和项目池迭代组和添加项目创建套一个项目设置一个项目,但仅添加项目时,他们比在每一组中的最后一个,也是最大的项目等于或大于:

{1} -> {1, 1}, {1, 2}, {1, 3} 
{2} -> {2, 2}, {2, 3} 
{3} -> {3, 3} 

现在你有一组T(1)+ T(2)+ T的(3)= 10项:

{} 
{1}, {2}, {3} 
{1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3} 

(T(n)是,¹/₂第n个三角形数·N·(N + 1))。

我不知道C#,但在伪代码,你的算法看起来是这样的:

var m = 3         // max. items 
var pool = {1, 2, 3}      // item pool 
var res = {{}}        // results, 
              // start with empty list 

var k = 0         // starting index of subarray 
              // with one fewer item 

while (m--) {        // loop m times 
    var kk = res.length()     // current result array length 

    for (var i = k; i < kk; i++) { 
     var j0 = 0 

     if (res[i].length() > 0) {   // find index of largest item 
      j0 = pool.index(res[i].last()) // from the set in pool 
     } 

     for (var j = j0; j p in pool {  // add new set 
      res.add(res[i] + {pool[j]}) 
     } 
    } 

    k = kold 
} 

这也可以递归实现,在那里你跟踪的最后一项指标在各级别,使您不必搜索它做。