Function to generate all subsets of size n

Question

The function works this way:

1. Set is an instance variable, and is an array of type generic.

2. nElement is the size of all the subsets that you want. For example if you give it the value 3 the function will return all the subsets of Set of size 3

3. The idea is that we create an array named indices (indices = index in French) that will follow the index that we want for each subset.

4. We know that all of our subsets have a size of 3 elements so if indices[2] = 3 we have to increment indices[1] by 1 and set all of the following indices[i] to indices[i-1]+1.

Example

Set = {1,2,3,4} nElement = 3

1. for the first subset the indices = {0,1,2} -> {1,2,3}

2. for the second subset the indices = {0,1,3} -> {1,2,4} indices[2] = 3 so we indices[1]++ and indices[2] = indices[1]+1

3. for the third subset the indices = {0,2,3} -> {1,3,4} indices[2] = indices[2] = 3 so we indices[1]++ and indices[2] = indices[1]+1 but indices[1] now = 2 and the max value that indices[1] can have is 2 so indices[0]++ and indices[1] = indices[0]+1

4. for the fourth subset the indices = {1,2,3} -> {2,3,4}

Code

public List<T[]> GenerateCoupleOf(int nElement)
{
 if (nElement < 1)
 throw new Exception("nElement must be greater than 0");
 List<T[]> tr = new List<T[]>();
 T[] arr;
 int[] indices = new int[nElement];
 T[] temp_arr = new T[nElement];
 for (int i = 0; i < indices.Length; i++)
 indices[i] = i;
 while (indices[0] <= Set.Length - 1 - ((Set.Length - 1) - (Set.Length - 1 - indices.Length + 0)) + 1)
 {
 for (int i = 0; i < indices.Length; i++)
 temp_arr[i] = Set[indices[i]];
 arr = new T[nElement];
 for (int i = 0; i < indices.Length; i++)
 arr[i] = Set[indices[i]];
 tr.Add(arr);
 indices[indices.Length - 1]++;
 for (int i = indices.Length - 1; i > 0; i--)
 {
 if (indices[i] > Set.Length - 1 - ((Set.Length - 1) - (Set.Length - 1 - indices.Length + i)) + 1)
 {
 indices[i - 1]++;
 for (int j = i; j < indices.Length; j++)
 indices[j] = indices[j - 1] + 1;
 }
 }
 }
 return tr;
}

• t3chb0t: Do you really call the method GenerateCoupleOf? Why don't post the entire class? The code is extremely hard to read.

Answer 1

Readability is a big factor in programming when it comes to maintaining the code by yourself or some other developer.
Readability can be improved by using standards which other developers expecting to see. Therefor some guidelines had been created like the .NET Naming Guidelines to name things like classes, properties, variables and parameters. Based on these guidlines variables should be named using camelCase casing instead of snake_case casing.

Omitting braces {} can lead to hidden and therfor hard to find bugs. i would like to encourage you to always use them.

That beeing said I will first focus on one part of your code...no, on two parts of your code but both are related.

while (indices[0] <= Set.Length - 1 - ((Set.Length - 1) - (Set.Length - 1 - indices.Length + 0)) + 1) 

and

if (indices[i] > Set.Length - 1 - ((Set.Length - 1) - (Set.Length - 1 - indices.Length + i)) + 1)

but lets focus on the right part of the first line

Set.Length - 1 - ((Set.Length - 1) - (Set.Length - 1 - indices.Length + 0)) + 1 

using simple math we can shorten this by removing the first () like so

Set.Length - 1 - (Set.Length - 1 - Set.Length + 1 + indices.Length - 0) + 1 

and by removing the remaining () like so

Set.Length - 1 - Set.Length + 1 + Set.Length - 1 - indices.Length + 0 + 1 

we get

Set.Length - indices.Length + 0 

which is just

Set.Length - nElement + 0 

which makes the while much more readable like so

int maxValueOfFirstIndex = Set.Length - nElement;
while (indices[0] <= maxValueOfFirstIndex)
{
}

which can be applied to the former if condition like so

if (indices[i] > maxValueOfFirstIndex + i)
{
} 

but nElement isn't as expressive as it could so numberOfItems could be a better name.

---

• The T[] temp_arr isn't used in a useful way. You can safely remove it.
• The check for nElement < 1 whouldn't throw an Exception but an ArgumentOutOfRangeException.
• because variables should be declared as near as possible to their usage you should move the declaration of T[] arr inside the while.

• by using Enumerable.Repeat().Select().ToArray() you can simplify the creation of indeces[] like so

  int[] indices = Enumerable.Repeat(0, nElement).Select((s, d) => s + d).ToArray();
  

• creating the T[] arr by a method would clean the main method as well
• using the var type instead of concrete types can help if you later need to refactor to use a different type. And its shorter to write hence easier to read, at least if the type can be seen clearly from the right hand side of the assignment.

  ---

Applying the mentioned points will lead to

public List<T[]> GenerateCoupleOf(int numberOfItems)
{
 if (numberOfItems < 1)
 {
 throw new ArgumentOutOfRangeException("numberOfItems", "Value must be greater than 0");
 }
 var tr = new List<T[]>();
 var indices = Enumerable.Repeat(0, numberOfItems).Select((s, d) => s + d).ToArray();
 var maxValueOfFirstIndex = Set.Length - numberOfItems;
 while (indices[0] <= maxValueOfFirstIndex)
 {
 T[] arr = CreateArrayByIndices(indices, numberOfItems);
 tr.Add(arr);
 indices[indices.Length - 1]++;
 for (var i = indices.Length - 1; i > 0; i--)
 {
 if (indices[i] > maxValueOfFirstIndex + i)
 {
 indices[i - 1]++;
 for (var j = i; j < indices.Length; j++)
 {
 indices[j] = indices[j - 1] + 1;
 }
 }
 }
 }
 return tr;
}
private T[] CreateArrayByIndices(int[] indices, int numberOfItems)
{
 var arr = new T[numberOfItems];
 for (int i = 0; i < indices.Length; i++)
 {
 arr[i] = Set[indices[i]];
 }
 return arr;
}