SHARE
TWEET

Permutations With Repetition

a guest Sep 29th, 2015 116 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Text;
  3. using System.Collections.Generic;
  4.  
  5. namespace _05.Permutations_Rep_v2
  6. {
  7.     class Permutations
  8.     {
  9.         static int totalPermutations = 0;
  10.  
  11.         static void Main()
  12.         {
  13.             //int[] set = new int[] { 1, 2, 3 };
  14.             //int[] set = new int[] { 1, 3, 3 };
  15.             //int[] set = new int[] { 1, 2, 3, 4 };
  16.             //int[] set = new int[] { 1, 3, 5, 5 };
  17.             //int[] set = new int[] { 1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 };
  18.             //int[] set = new int[] { 5, 1, 3, 5, 5 };
  19.             int[] set = new int[] { 1, 5, 5, 7, 7, 7, 1 };
  20.  
  21.             OccurrencesCounter<int> setCounter = new OccurrencesCounter<int>();
  22.             for (var i = 0; i < set.Length; i++)
  23.             {
  24.                 setCounter.Add(set[i]);
  25.             }
  26.             Console.WriteLine(setCounter.ToString());
  27.  
  28.             int[] arr = new int[set.Length];
  29.             bool[] busy = new bool[set.Length];
  30.             permute(setCounter, set.Length, 0, 0, -1, arr, busy);
  31.             Console.WriteLine("Total Items in Set: {0}", set.Length);
  32.             Console.WriteLine("Total Permutations: {0}", totalPermutations);
  33.         }
  34.  
  35.         static void permute(OccurrencesCounter<int> set, int n, int numberIndex, int numberOccurenceIndex, int numberLastIndexPlacement, int[] arr, bool[] busy)
  36.         {
  37.             if (numberIndex >= set.Count)
  38.             {
  39.                 Print(arr);
  40.                 totalPermutations++;
  41.             }
  42.             else
  43.             {
  44.                 KeyValuePair<int, int> currNumber = set[numberIndex];
  45.                 if (numberOccurenceIndex >= currNumber.Value)
  46.                 {
  47.                     permute(set, n, numberIndex + 1, 0, -1, arr, busy);
  48.                 }
  49.                 else
  50.                 {
  51.                     var start = Math.Max(numberOccurenceIndex, numberLastIndexPlacement);
  52.                     var end = n + numberOccurenceIndex - currNumber.Value + 1;
  53.                     for (var i = start; i < end; i++)
  54.                     {
  55.                         if (busy[i]) continue;
  56.                         arr[i] = currNumber.Key;
  57.                         busy[i] = true;
  58.                         permute(set, n, numberIndex, numberOccurenceIndex + 1, i, arr, busy);
  59.                         busy[i] = false;
  60.                     }
  61.                 }
  62.             }
  63.         }
  64.  
  65.         private static void Print(int[] array)
  66.         {
  67.             Console.WriteLine("{{ {0} }}", string.Join(", ", array));
  68.         }
  69.     }
  70.    
  71.     public class OccurrencesCounter<T>
  72.     {
  73.         public class ListNode<T>
  74.         {
  75.             public T Value { get; private set; }
  76.             public int OccurrencesCount { get; set; }
  77.             public ListNode<T> NextNode { get; set; }
  78.             public ListNode()
  79.             {
  80.             }
  81.             public ListNode(T value, ListNode<T> next)
  82.             {
  83.                 this.Value = value;
  84.                 this.NextNode = next;
  85.                 this.OccurrencesCount = 0;
  86.             }
  87.         }
  88.  
  89.         private ListNode<T> Head;
  90.         private ListNode<T> Tail;
  91.         public int Count { get; private set; }
  92.  
  93.         public void Add(T value)
  94.         {
  95.             if (this.Count == 0)
  96.             {
  97.                 var node = new ListNode<T>(value, null);
  98.                 node.OccurrencesCount++;
  99.                 this.Head = node;
  100.                 this.Tail = node;
  101.                 this.Count++;
  102.             }
  103.             else
  104.             {
  105.                 bool found = false;
  106.                 ListNode<T> temp = null;
  107.                 for (var i = 0; i < this.Count; i++)
  108.                 {
  109.                     if (i == 0) temp = this.Head;
  110.  
  111.                     if (value.Equals(temp.Value))
  112.                     {
  113.                         temp.OccurrencesCount++;
  114.                         found = true;
  115.                         break;
  116.                     }
  117.                     temp = temp.NextNode;
  118.                 }
  119.  
  120.                 if (found == false)
  121.                 {
  122.                     var node = new ListNode<T>(value, null);
  123.                     node.OccurrencesCount++;
  124.                     this.Tail.NextNode = node;
  125.                     this.Tail = node;
  126.                     this.Count++;
  127.                 }
  128.             }
  129.         }
  130.  
  131.         public Dictionary<T, int> ToDictionary()
  132.         {
  133.             Dictionary<T, int> dict = new Dictionary<T, int>();
  134.             ListNode<T> temp = null;
  135.             for (var i = 0; i < this.Count; i++)
  136.             {
  137.                 if (i == 0)
  138.                 {
  139.                     temp = this.Head;
  140.                 }
  141.                 dict[temp.Value] = temp.OccurrencesCount;
  142.                 temp = temp.NextNode;
  143.             }
  144.             return dict;
  145.         }
  146.  
  147.         public KeyValuePair<T, int> this[int index]
  148.         {
  149.             get
  150.             {
  151.                 if (index >= this.Count)
  152.                 {
  153.                     throw new IndexOutOfRangeException("OccurrencesCounter indexer problem.");
  154.                 }
  155.                 ListNode<T> temp = null;
  156.                 for (var i = 0; i < this.Count; i++)
  157.                 {
  158.                     if (i == 0)
  159.                     {
  160.                         temp = this.Head;
  161.                     }
  162.                     if (i == index)
  163.                     {
  164.                         return new KeyValuePair<T, int>(temp.Value, temp.OccurrencesCount);
  165.                     }
  166.                     temp = temp.NextNode;
  167.                 }
  168.                 return new KeyValuePair<T, int>();
  169.             }
  170.         }
  171.  
  172.         public override string ToString()
  173.         {
  174.             StringBuilder str = new StringBuilder();
  175.             ListNode<T> temp = new ListNode<T>();
  176.             for (var i = 0; i < this.Count; i++)
  177.             {
  178.                 if (i == 0)
  179.                 {
  180.                     temp = this.Head;
  181.                 }
  182.                 str.Append(string.Format("{0} => {1}\n", temp.Value, temp.OccurrencesCount));
  183.                 temp = temp.NextNode;
  184.             }
  185.             return str.ToString();
  186.         }
  187.     }
  188. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top