How to resolve the algorithm Permutations step by step in the C# programming language

Published on 12 May 2024 09:40 PM
#C_Sharp

How to resolve the algorithm Permutations step by step in the C# programming language

Table of Contents

Problem Statement

Write a program that generates all   permutations   of   n   different objects.   (Practically numerals!)

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Permutations step by step in the C# programming language

Extension Method approach

The first solution defines an extension method called Permutations for any type of list of elements that implement the IComparable interface. The Permutations method generates all possible permutations of the list by recursively calling itself on smaller sublists. The base case is when the list contains only one element, in which case it returns a list with that element. For larger lists, the method iterates over each element, and for each element, it calls itself on the sublist of all the other elements and adds the current element to the front of each permutation generated by the recursive call.

Class approach

The second solution defines a class called Permutations with a static method called AllFor that takes an array of elements and returns an enumerable of all possible permutations of the array. The algorithm used by the AllFor method is a recursive backtracking algorithm that iterates over all possible combinations of elements in the array, swapping elements as needed to generate all permutations.

Main() function approach

The third solution defines a Main function which is the entry point of the program. It creates an array of strings and then calls the rec function which prints all possible permutations of the array. The rec function takes an index as an argument and recursively calls itself on the subarray of the array starting at that index. The base case is when the index is equal to the length of the array, in which case it prints the current permutation.

Backtracking approach

The fourth solution defines a class called Permutations with a static method called Main that takes no arguments. The Main method creates an array of integers and then calls the rec function which prints all possible permutations of the array. The rec function takes an index as an argument and recursively calls itself on the subarray of the array starting at that index. The base case is when the index is equal to the length of the array, in which case it prints the current permutation.

Heap's algorithm

The fifth solution defines a static method called HeapsPermutations which takes an array of elements and returns an enumerable of all possible permutations of the array. Heap's algorithm is a non-recursive algorithm that generates all permutations of an array by repeatedly swapping elements in the array. The algorithm starts by finding the smallest element in the array that is not in its final position. It then swaps that element with the element in its final position and recursively applies the algorithm to the subarray of the array starting at the next index. The algorithm terminates when the subarray is empty, which means that all permutations have been generated.

Source code in the csharp programming language

public static class Extension
{
    public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> values) where T : IComparable<T>
    {
        if (values.Count() == 1)
            return new[] { values };
        return values.SelectMany(v => Permutations(values.Where(x => x.CompareTo(v) != 0)), (v, p) => p.Prepend(v));
    }
}


Enumerable.Range(0,5).Permutations()

public class Permutations<T>
{
    public static System.Collections.Generic.IEnumerable<T[]> AllFor(T[] array)
    {
        if (array == null || array.Length == 0)
        {
            yield return new T[0];
        }
        else
        {
            for (int pick = 0; pick < array.Length; ++pick)
            {
                T item = array[pick];
                int i = -1;
                T[] rest = System.Array.FindAll<T>(
                    array, delegate(T p) { return ++i != pick; }
                );
                foreach (T[] restPermuted in AllFor(rest))
                {
                    i = -1;
                    yield return System.Array.ConvertAll<T, T>(
                        array,
                        delegate(T p) {
                            return ++i == 0 ? item : restPermuted[i - 1];
                        }
                    );
                }
            }
        }
    }
}


namespace Permutations_On_RosettaCode
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] list = "a b c d".Split();
            foreach (string[] permutation in Permutations<string>.AllFor(list))
            {
                System.Console.WriteLine(string.Join(" ", permutation));
            }
        }
    }
}


using System;
class Permutations
{
  static int n = 4;
  static int [] buf = new int [n];
  static bool [] used = new bool [n];

  static void Main()
  {
    for (int i = 0; i < n; i++) used [i] = false;
    rec(0);
  }

  static void rec(int ind)
  {
    for (int i = 0; i < n; i++)
    {
      if (!used [i])
      {
        used [i] = true;
        buf [ind] = i;
	if (ind + 1 < n) rec(ind + 1);
        else Console.WriteLine(string.Join(",", buf));
	used [i] = false;
      }
    }
  }
}


using System;
class Permutations
{
  static int n = 4;
  static int [] buf = new int [n];
  static int [] next = new int [n+1];

  static void Main()
  {
    for (int i = 0; i < n; i++) next [i] = i + 1;
    next[n] = 0;
    rec(0);
  }

  static void rec(int ind)
  {
    for (int i = n; next[i] != n; i = next[i])
    {                              
      buf [ind] = next[i];
      next[i]=next[next[i]];
      if (ind < n - 1) rec(ind + 1);
      else Console.WriteLine(string.Join(",", buf));
      next[i] = buf [ind];
    }
  }
}


// Always returns the same array which is the one passed to the function
public static IEnumerable<T[]> HeapsPermutations<T>(T[] array)
{
    var state = new int[array.Length];

    yield return array;

    for (var i = 0; i < array.Length;)
    {
        if (state[i] < i)
        {
            var left = i % 2 == 0 ? 0 : state[i];
            var temp = array[left];
            array[left] = array[i];
            array[i] = temp;
            yield return array;
            state[i]++;
            i = 1;
        }
        else
        {
            state[i] = 0;
            i++;
        }
    }
}

// Returns a different array for each permutation
public static IEnumerable<T[]> HeapsPermutationsWrapped<T>(IEnumerable<T> items)
{
    var array = items.ToArray();
    return HeapsPermutations(array).Select(mutating =>
        {
            var arr = new T[array.Length];
            Array.Copy(mutating, arr, array.Length);
            return arr;
        });
}

You may also check:How to resolve the algorithm Motzkin numbers step by step in the Mathematica/Wolfram Language programming language
You may also check:How to resolve the algorithm Comments step by step in the TPP programming language
You may also check:How to resolve the algorithm Sisyphus sequence step by step in the J programming language
You may also check:How to resolve the algorithm Gaussian elimination step by step in the JavaScript programming language
You may also check:How to resolve the algorithm Menu step by step in the Perl programming language