How to create a 2 dimensional permutation structure in C#

I have the following

1000 people
50 objects

Some "rules"

Each person must have exactly 1 object
All people can have the same object (people can share an object)
Not all objects have to be used

I want to chart out the permutations - How would I go about generating this structure in say C#?

I've currently just been randomly selecting an object for a person and remembering what I selected so I don't select it again in the next iteration - not useful I know.

Solution

Having 100 people and 50 objects you are going to have

100 ^ 50 = 1e100  # `^` means raising into power

googol solutions; it's by far more than elementary particles in the visible part of the Universe. That's why let not materialize the solution into any collection (2d array etc. - we are not looking for OutOfMemoryException) but enumerate them; at least you can stop enumerating whenever you want:

Code:

using System.Linq;
...
private static IEnumerable<(K key, V value)[]> MySampling<K, V>(IEnumerable<K> keys, 
                                                                IEnumerable<V> values) {
  if (keys is null)
    throw new ArgumentNullException(nameof(keys));
  if (values is null)
    throw new ArgumentNullException(nameof(values));

  IReadOnlyList<K> keysList = keys is IReadOnlyList<K> keysFound 
    ? keysFound : keys.ToList();
  IReadOnlyList<V> valuesList = values is IReadOnlyList<V> valuesFound 
    ? valuesFound : values.ToList();

  if (keysList.Count <= 0 || valuesList.Count <= 0)
    yield break;

  int[] indexes = new int[keysList.Count];

  do {
    yield return Enumerable
      .Range(0, keysList.Count)
      .Select(i => (key: keysList[i], value: valuesList[indexes[i]]))
      .ToArray();

    for (int i = indexes.Length - 1; i >= 0; --i)
      if (++indexes[i] == valuesList.Count)
        indexes[i] = 0;
      else
        break;
  } 
  while (indexes.Any(index => index != 0));
}

Demo:

char[] people = { 'A', 'B', 'C', 'D' };
int[] objects = { 1, 2, 3 };

var result = MySampling(people, objects);

var report = string.Join(Environment.NewLine, result
  .Select(line => string.Join(" ", line.Select(item => $"({item.key} : {item.value})"))));

Console.Write(report);

Output:

(A : 1) (B : 1) (C : 1) (D : 1) # all people - A, B, C, D - chose 1st object
(A : 1) (B : 1) (C : 1) (D : 2) # people A, B, C chose 1st, D chose 2nd object
(A : 1) (B : 1) (C : 1) (D : 3)
(A : 1) (B : 1) (C : 2) (D : 1)
(A : 1) (B : 1) (C : 2) (D : 2)
(A : 1) (B : 1) (C : 2) (D : 3)
(A : 1) (B : 1) (C : 3) (D : 1)
(A : 1) (B : 1) (C : 3) (D : 2)
(A : 1) (B : 1) (C : 3) (D : 3)
(A : 1) (B : 2) (C : 1) (D : 1)
(A : 1) (B : 2) (C : 1) (D : 2)
(A : 1) (B : 2) (C : 1) (D : 3)
(A : 1) (B : 2) (C : 2) (D : 1)
(A : 1) (B : 2) (C : 2) (D : 2)
(A : 1) (B : 2) (C : 2) (D : 3)
(A : 1) (B : 2) (C : 3) (D : 1)
(A : 1) (B : 2) (C : 3) (D : 2)
(A : 1) (B : 2) (C : 3) (D : 3)
(A : 1) (B : 3) (C : 1) (D : 1)
(A : 1) (B : 3) (C : 1) (D : 2)
(A : 1) (B : 3) (C : 1) (D : 3)
(A : 1) (B : 3) (C : 2) (D : 1)
(A : 1) (B : 3) (C : 2) (D : 2)
(A : 1) (B : 3) (C : 2) (D : 3)
(A : 1) (B : 3) (C : 3) (D : 1)
(A : 1) (B : 3) (C : 3) (D : 2)
(A : 1) (B : 3) (C : 3) (D : 3)
(A : 2) (B : 1) (C : 1) (D : 1)
(A : 2) (B : 1) (C : 1) (D : 2)
(A : 2) (B : 1) (C : 1) (D : 3)
(A : 2) (B : 1) (C : 2) (D : 1)
(A : 2) (B : 1) (C : 2) (D : 2)
(A : 2) (B : 1) (C : 2) (D : 3)
(A : 2) (B : 1) (C : 3) (D : 1)
(A : 2) (B : 1) (C : 3) (D : 2)
(A : 2) (B : 1) (C : 3) (D : 3)
(A : 2) (B : 2) (C : 1) (D : 1)
(A : 2) (B : 2) (C : 1) (D : 2)
(A : 2) (B : 2) (C : 1) (D : 3)
(A : 2) (B : 2) (C : 2) (D : 1)
(A : 2) (B : 2) (C : 2) (D : 2)
(A : 2) (B : 2) (C : 2) (D : 3)
(A : 2) (B : 2) (C : 3) (D : 1)
(A : 2) (B : 2) (C : 3) (D : 2)
(A : 2) (B : 2) (C : 3) (D : 3)
(A : 2) (B : 3) (C : 1) (D : 1)
(A : 2) (B : 3) (C : 1) (D : 2)
(A : 2) (B : 3) (C : 1) (D : 3)
(A : 2) (B : 3) (C : 2) (D : 1)
(A : 2) (B : 3) (C : 2) (D : 2)
(A : 2) (B : 3) (C : 2) (D : 3)
(A : 2) (B : 3) (C : 3) (D : 1)
(A : 2) (B : 3) (C : 3) (D : 2)
(A : 2) (B : 3) (C : 3) (D : 3)
(A : 3) (B : 1) (C : 1) (D : 1)
(A : 3) (B : 1) (C : 1) (D : 2)
(A : 3) (B : 1) (C : 1) (D : 3)
(A : 3) (B : 1) (C : 2) (D : 1)
(A : 3) (B : 1) (C : 2) (D : 2)
(A : 3) (B : 1) (C : 2) (D : 3)
(A : 3) (B : 1) (C : 3) (D : 1)
(A : 3) (B : 1) (C : 3) (D : 2)
(A : 3) (B : 1) (C : 3) (D : 3)
(A : 3) (B : 2) (C : 1) (D : 1)
(A : 3) (B : 2) (C : 1) (D : 2)
(A : 3) (B : 2) (C : 1) (D : 3)
(A : 3) (B : 2) (C : 2) (D : 1)
(A : 3) (B : 2) (C : 2) (D : 2)
(A : 3) (B : 2) (C : 2) (D : 3)
(A : 3) (B : 2) (C : 3) (D : 1)
(A : 3) (B : 2) (C : 3) (D : 2)
(A : 3) (B : 2) (C : 3) (D : 3)
(A : 3) (B : 3) (C : 1) (D : 1)
(A : 3) (B : 3) (C : 1) (D : 2)
(A : 3) (B : 3) (C : 1) (D : 3)
(A : 3) (B : 3) (C : 2) (D : 1)
(A : 3) (B : 3) (C : 2) (D : 2)
(A : 3) (B : 3) (C : 2) (D : 3)
(A : 3) (B : 3) (C : 3) (D : 1)
(A : 3) (B : 3) (C : 3) (D : 2)
(A : 3) (B : 3) (C : 3) (D : 3)