How can I save the output of heapPermutations as a list?

Question

static void printArr(int[] a, int n)
        {
            for (int i = 0; i < n; i++)
                Console.Write(a[i] + " ");
            Console.WriteLine();
        }

        // Generating permutation using Heap Algorithm
        static void heapPermutation(int[] a, int size, int n)
        {
            // if size becomes 1 then prints the obtained
            // permutation
            if (size == 1)
                printArr(a, n);

            for (int i = 0; i < size; i++)
            {
                heapPermutation(a, size - 1, n);

                // if size is odd, swap 0th i.e (first) and
                // (size-1)th i.e (last) element
                if (size % 2 == 1)
                {
                    int temp = a[0];
                    a[0] = a[size - 1];
                    a[size - 1] = temp;
                }

                // If size is even, swap ith and
                // (size-1)th i.e (last) element
                else
                {
                    int temp = a[i];
                    a[i] = a[size - 1];
                    a[size - 1] = temp;
                }
            }
        }

I'm trying to use Heap's Algorithm to find all the permutations of some list, and then I want to save all the permutations as a list of lists, but I'm not sure how to do this. Most online implementations I find involve setting the output as void.

I tried to specify the output as a list, but I'd run into an error saying not all code paths return a value. I think I need to include a return statement in the code in order to get an output of list containing lists, but I'm not really sure.

Answer 1

I suggest implementing a generator, i.e. return IEnumerable<List<T>> - enumeration of permutaions:

using System.Collections.Generic;
using System.Linq;

...

// Let's generalize solution - permutation of any (not necessary integer)
// distinct items
private static IEnumerable<List<T>> Permutate<T>(IEnumerable<T> array) {
  yield return array.ToList();
    
  // let's not modify initial array
  T[] a = array.ToArray();
  int n = a.Length;

  int[] c = new int[a.Length]; 

  for (int i = 1; i < n; ++i) {
    if (c[i] < i) {
      if (i % 2 == 0)
        (a[0], a[i]) = (a[i], a[0]);
      else 
        (a[i], a[c[i]]) = (a[c[i]], a[i]);

      yield return a.ToList();

      c[i] += 1;

      i = 0;
    }
    else 
      c[i] = 0;
  }
}

Then you can get List<T>:

char[] data = new char[] { 'A', 'B', 'C' };

List<List<char>> result = Permutate(data);

Or print

char[] data = new char[] { 'A', 'B', 'C' };

var result = string.Join(Environment.NewLine, Permutate(data)
  .Select(item => string.Join(" ", item))); 
        
Console.WriteLine(result);

Output:

A B C
B A C
C A B
A C B
B C A
C B A

Fiddle

Edit: Since Permutate<T> is a generic, you don't have to modify it, all you should do is to call:

// All you have to do is to specify input
int[] data = new int[] { 1, 2, 3 };

// All the rest will be the same
var result = string.Join(Environment.NewLine, Permutate(data)
  .Select(item => string.Join(" ", item))); 
        
Console.WriteLine(result);