Unique combinations of sets with N min selections of overall set

Question

I'm in the process of attempting to write a parser compiler. In this, sets play a major role. I'm in the 'lexical ambiguity' isolation phase, and to that, I need to yield a set of every possible permutation of a given set of items which represent an ambiguity.

An ambiguity is reached when there are at two or more items in the active context that are lexically identical, but differ by their defined identity (The contextual keyword 'from' versus an Identifier of 'from'.)

That being said, I first detect the ambiguities of the language, and generate a set of sets which represent the full extent of each ambiguity. Upon each set I then need to yield all permutations of two or greater. Below is the initial result that appears, upon testing, to do what I want, but I went overboard and have a method that operates on multiple sets, so if given: { 'a', 'b' } and { 'c', 'd' } it would yield { 'a', 'c' }, { 'a', 'd' }, { 'b', 'c' }, and { 'b', 'd' }, which I solved with the 'Splay' method.

public static IEnumerable<IEnumerable<T>> Splay<T>(this IEnumerable<T> series)
{
  /* When you want to yield an enumerable over each element in the series. */
  foreach (var element in series)
    yield return new T[1] { element };
}

public static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(int minSetLength, params T[][] series)
{
  return GetAllPermutations(minSetLength,
    (IEnumerable<IEnumerable<T>>)series);
}

public static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(int minSetLength, IEnumerable<IEnumerable<T>> series)
{
  var jaggedVariation =
    series.Select(set => set.ToArray()).ToArray();
  for (int minDepth = minSetLength; minDepth <= jaggedVariation.Length; minDepth++)
    foreach (var set in GetPermutationsOfLength<T>(minDepth, jaggedVariation))
      yield return set;
}

private static IEnumerable<IEnumerable<T>> GetPermutationsOfLength<T>(int elementsPerSet, T[][] series)
{
  for (int subsetIndex = 0; subsetIndex < series.Length - (elementsPerSet - 1); subsetIndex++)
    foreach (var subset in GetPermutationsOfLength<T>(elementsPerSet, subsetIndex, 0, series).Select(k=>k.ToArray()))
      if (subset.Length == elementsPerSet) /* Keeps the logic below very simple. */
        yield return subset;
}

private static IEnumerable<IEnumerable<T>> GetPermutationsOfLength<T>(int elementsPerSet, int startingAt, int currentLength, T[][] series)
{
  if (startingAt >= series.Length || currentLength >= elementsPerSet)
    yield break;

  var currentFrontSet = series[startingAt];
  foreach (var forefront in currentFrontSet)
  {
    var forefrontSet = new T[1] { forefront };
    /* Continue expanding recursively until the above constraints cause it to short circuit. */
    for (int i = startingAt + 1; i < series.Length; i++)
    {
      var subsets = GetPermutationsOfLength<T>(elementsPerSet, i, currentLength + 1, series);
      foreach (var subset in subsets)
        yield return forefrontSet.Concat(subset);
    }
    yield return forefrontSet;
  }
}

I'll be calling this with a single array that I call Splay on due to my over eagerness, but the general idea is I need every possible combination with two or greater elements, with no repeats. So if an ambiguity represents 5 separate identities I would yield 26 different sets, two through five items long. Each permutation within these ambiguity sets would become unique identities themselves, and have a bit mask I could check against unambiguous transition tables to identify the specific ambiguity, unify that ambiguity to determine the proper follow set and how to differentiate which identity it once was.

Does anyone have any suggestions/insight on the approach? I tried to keep the approach simple: I used iterators due to the simplicity they provide. They will have a slight memory footprint due to the allocation of the iterator objects and the lifting of the locals; however, the environment this runs in is already utilizing 6+GB of memory to handle unbound look-ahead ambiguity resolution, so this is just another step.

Answer 1

public static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(int minSetLength, IEnumerable<IEnumerable<T>> series)
{
  var jaggedVariation =
series.Select(set => set.ToArray()).ToArray();
  for (int minDepth = minSetLength; minDepth <= jaggedVariation.Length; minDepth++)
    foreach (var set in GetPermutationsOfLength<T>(minDepth, jaggedVariation))
      yield return set;
}

Firstly, I don't like the absence of braces in your loops. I know it's technically correct, but it makes it a lot harder to parse in your head, and if you ever want to add an extra statement in there, you're going to have to go in and surround it with braces first, or you'll get some really weird errors.

public static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(int minSetLength, IEnumerable<IEnumerable<T>> series)
{
    var jaggedVariation = series.Select(set => set.ToArray()).ToArray();

    for (int minDepth = minSetLength; minDepth <= jaggedVariation.Length; minDepth++)
    {
        foreach (var set in GetPermutationsOfLength<T>(minDepth, jaggedVariation))
        {
            yield return set;
        }
    }
}

Secondly, your calls to ToArray don't make much sense to me. All your functions are returning IEnumerable<IEnumerable<T>>, but they all take T[][]. Why not simplify the whole affair by accepting IEnumerable<IEnumerable<T>> too?

But let's look closer. For your methods, when do you actually need an array?

public static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(int minSetLength, params T[][] series)
{
  return GetAllPermutations(minSetLength,
    (IEnumerable<IEnumerable<T>>)series);
}

Not here, you're literally casting it to IEnumerable<IEnumerable<T>> and that's it.

public static IEnumerable<IEnumerable<T>> GetAllPermutations<T>(int minSetLength, IEnumerable<IEnumerable<T>> series)
{
  var jaggedVariation =
    series.Select(set => set.ToArray()).ToArray();
  for (int minDepth = minSetLength; minDepth <= jaggedVariation.Length; minDepth++)
    foreach (var set in GetPermutationsOfLength<T>(minDepth, jaggedVariation))
      yield return set;
}

Certainly not here, and cutting out all those ToArray() calls will cut down on execution time.

private static IEnumerable<IEnumerable<T>> GetPermutationsOfLength<T>(int elementsPerSet, T[][] series)
{
  for (int subsetIndex = 0; subsetIndex < series.Length - (elementsPerSet - 1); subsetIndex++)
    foreach (var subset in GetPermutationsOfLength<T>(elementsPerSet, subsetIndex, 0, series).Select(k=>k.ToArray()))
      if (subset.Length == elementsPerSet) /* Keeps the logic below very simple. */
        yield return subset;
}

Not here, either, Length can be substituted for a call to Count(). That'll cut out both a .ToArray() and a Select() call.

private static IEnumerable<IEnumerable<T>> GetPermutationsOfLength<T>(int elementsPerSet, int startingAt, int currentLength, T[][] series)
{
  if (startingAt >= series.Length || currentLength >= elementsPerSet)
    yield break;

  var currentFrontSet = series[startingAt];
  foreach (var forefront in currentFrontSet)
  {
    var forefrontSet = new T[1] { forefront };
    /* Continue expanding recursively until the above constraints cause it to short circuit. */
    for (int i = startingAt + 1; i < series.Length; i++)
    {
      var subsets = GetPermutationsOfLength<T>(elementsPerSet, i, currentLength + 1, series);
      foreach (var subset in subsets)
        yield return forefrontSet.Concat(subset);
    }
    yield return forefrontSet;
  }
}

And not here, either. Length can be replaced by Count() and the one time you're getting something by index, you can simply call ElementAt(x) or, if you must, convert it to a List or an Array here.

Answer 2

The approach works. After further evaluating the needs of the use case, I determined that there on average very few actual permutations, even on larger languages.

A majority of this was obviated due to token precedences. 'Performance' matters, but only when you're dealing with very large sets, the results I was getting were... under a hundred subsets. Once I handled unbound look-ahead and follow projection, I reduced that set of ambiguities to those which actually surfaced in the result language and only about 16 actually appear as used.

Worrying about the small set of items that result in the scope of the other 110 million+ computations that take 6GB+ ended up being quite unnecessary.