Reputation: 5637
How would I go about generating a list of all combinations of words up to a certain length from a List<string>
source?
For example, I have a List<string>
of 10,600+ words which I need to convert to a List<List<string>>
, however, the sub list only needs to contain combinations up to and including a given maximum length, for this example, I'll say 3.
I don't care about the order in which the words appear in the sub list. For example, I only need 1 of the following in the list:
"laptop", "computer", "reviews"
"laptop", "reviews", "computer"
"computer", "laptop", "reviews"
"computer" "reviews", "laptop"
"reviews", "computer", "laptop"
"reviews", "laptop", "computer"
Is it even possible given the large number of combinations I would need to generate?
Any help is much appreciated.
Upvotes: 1
Views: 2597
Reputation: 2171
private List<List<string>> GetCombinations()
{
List<List<string>> mResult= new List<List<string>>();
for (int i = 0; i < mList.Count; i++)
{
for (int k = 0; k < mList.Count; k++)
{
if (i == k) continue;
List<string> tmpList = new List<string>();
tmpList.Add(mList[i]);
int mCount = 1;
int j = k;
while (true)
{
if (j >= mList.Count) j = 0;
if (i != j)
{
tmpList.Add(mList[j]);
mCount++;
}
j += 1;
if (mCount >= mList.Count) break;
}
mResult.Add(tmpList);
}
}
return mResult;
}
Upvotes: 0
Reputation: 6101
First of all, I'm not sure that you really want to generate such huge list. If you really do, then I suggest you to consider to use iterators for lazy list generation instead of this huge list:
static void Main()
{
var words = new List<string> {"w1", "w2", "w3", "w4", "w5", "w6", "w7"};
foreach (var list in Generate(words, 3))
{
Console.WriteLine(string.Join(", ", list));
}
}
static IEnumerable<List<string>> Generate(List<string> words, int length, int ix = 0, int[] indexes = null)
{
indexes = indexes ?? Enumerable.Range(0, length).ToArray();
if (ix > 0)
yield return indexes.Take(ix).Select(x => words[x]).ToList();
if (ix > length)
yield break;
if (ix == length)
{
yield return indexes.Select(x => words[x]).ToList();
}
else
{
for (int jx = ix > 0 ? indexes[ix-1]+1 : 0; jx < words.Count; jx++)
{
indexes[ix] = jx;
foreach (var list in Generate(words, length, ix + 1, indexes))
yield return list;
}
}
}
Upvotes: 6
Reputation: 5566
i suppose the problem is mostly to check if a combination of words exists already in the list:
what you can do for that:
//generate a dictionary with key hashcode / value list of string
Dictionary<int, List<string>> validCombinations= new Dictionary<int, List<string>>();
//generating anyway your combinations (looping through the words)
List<string> combinationToCheck = new List<string>(){"reviews", "laptop", "computer"};
//sort the words
combinationToCheck.Sort();
string combined = String.Join("", combinationToCheck.ToArray());
//calculate a hash
int hashCode = combined.GetHashCode();
//add the combination if the same hash doesnt exist yet
if(!validCombinations.ContainsKey(hashCode))
validCombinations.Add(hashCode, combinationToCheck);
Upvotes: 0
Reputation: 10118
Hopefully I didn't mess with anything.
for(int i = 0; i < list.Count; i ++)
{
list1 = new List<string> { list[i] };
listcombinations.Add(list1);
for(int j = i + 1; j < list.Count; j ++)
{
list1 = new List<string> { list[i], list[j] };
listcombinations.Add(list1);
for(int k = j + 1; k < list.Count; k ++)
{
list1 = new List<string> { list[i], list[j], list[k] };
listcombinations.Add(list1);
}
}
}
Upvotes: 0