How to create a 2 dimensional permutation structure in C#-CodePudding

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.

CodePudding user response：

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)

CodePudding user response：

To create a two-dimensional permutation structure in C#, you can use a two-dimensional array, where each element represents an element in the permutation. You can then implement a method to generate the permutations using a recursive approach.

Here is an example of how you could implement a permutation generator for a two-dimensional array:

namespace PermutationGenerator
{
    class Program
    {
        static void Main(string[] args)
        {
            // Create the array to store the permutation
            int[,] permutation = new int[3, 3]
            {
                { 1, 2, 3 },
                { 4, 5, 6 },
                { 7, 8, 9 }
            };

            // Generate the permutations
            GeneratePermutations(permutation, 0, 0);
        }

        static void GeneratePermutations(int[,] permutation, int x, int y)
        {
            if (x == permutation.GetLength(0) - 1 && y == permutation.GetLength(1) - 1)
            {
                // Print the permutation
                for (int i = 0; i < permutation.GetLength(0); i  )
                {
                    for (int j = 0; j < permutation.GetLength(1); j  )
                    {
                        Console.Write(permutation[i, j]   " ");
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
                return;
            }

            int nextX = x;
            int nextY = y   1;
            if (y == permutation.GetLength(1) - 1)
            {
                nextX  ;
                nextY = 0;
            }

            // Generate permutations with the current element fixed
            GeneratePermutations(permutation, nextX, nextY);

            // Generate permutations by swapping the current element with the other elements
            for (int i = x; i < permutation.GetLength(0); i  )
            {
                for (int j = 0; j < permutation.GetLength(1); j  )
                {
                    if (i == x && j < y) continue;
                    Swap(ref permutation[x, y], ref permutation[i, j]);
                    GeneratePermutations(permutation, nextX, nextY);
                    Swap(ref permutation[x, y], ref permutation[i, j]);
                }
            }
        }

        static void Swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
    }
}

This code will generate all possible permutations of the two-dimensional array and print them to the console. Note that this will generate a lot of permutations, so it may take a long time to complete.