fork(1) download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace AllBalancedTrees
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             char[] nodes = { 'A', 'B', 'C', 'D', 'E' };
  13.  
  14.             AllBalancedTrees<char> AllBalancedTrees = new AllBalancedTrees<char>(); 
  15.  
  16.             foreach (char[] a in AllBalancedTrees.allBalancedTreeCombinations(nodes))
  17.             {
  18.                 foreach (char c in a)
  19.                 {
  20.                     Console.Write(c + " ");
  21.                 }
  22.                 Console.WriteLine();
  23.             }
  24.  
  25.             Console.ReadKey();
  26.         }
  27.     }
  28.  
  29.     class AllBalancedTrees<T>
  30.     {
  31.         public IEnumerable<T[]> allBalancedTreeCombinations(T[] nodes)
  32.         {
  33.             T[] result;
  34.             if (nodes.Length == 1)
  35.             {
  36.                 yield return nodes;
  37.             }
  38.             else if (nodes.Length == 2)
  39.             {
  40.                 yield return nodes;
  41.                 T[] nodes2 = new T[2];
  42.                 nodes2[0] = nodes[1];
  43.                 nodes2[1] = nodes[0];
  44.                 yield return nodes2;
  45.             }
  46.             else if (nodes.Length % 2 == 1)
  47.             {
  48.                 int mid = (nodes.Length - 1) / 2;
  49.                 T[] left = new T[mid];
  50.                 T[] right = new T[mid];
  51.                 Array.Copy(nodes, 0, left, 0, mid);
  52.                 Array.Copy(nodes, mid + 1, right, 0, mid);
  53.                 foreach (T[] l in allBalancedTreeCombinations(left))
  54.                 {
  55.                     foreach (T[] r in allBalancedTreeCombinations(right))
  56.                     {
  57.                         result = new T[nodes.Length];
  58.                         result[0] = nodes[mid];
  59.                         foreach (T[] a in allMergeCombinations(l, r))
  60.                         {
  61.                             Array.Copy(a, 0, result, 1, a.Length);
  62.                             yield return result;
  63.                         }
  64.                     }
  65.                 }
  66.             }
  67.             else
  68.             {
  69.                 int mid = (nodes.Length) / 2;
  70.                 T[] left = new T[mid];
  71.                 T[] right = new T[mid - 1];
  72.                 Array.Copy(nodes, 0, left, 0, mid);
  73.                 Array.Copy(nodes, mid + 1, right, 0, mid - 1);
  74.                 foreach (T[] l in allBalancedTreeCombinations(left))
  75.                 {
  76.                     foreach (T[] r in allBalancedTreeCombinations(right))
  77.                     {
  78.                         result = new T[nodes.Length];
  79.                         result[0] = nodes[mid];
  80.                         foreach (T[] a in allMergeCombinations(l, r))
  81.                         {
  82.                             Array.Copy(a, 0, result, 1, a.Length);
  83.                             yield return result;
  84.                         }
  85.                     }
  86.                 }
  87.  
  88.                 mid = nodes.Length / 2 - 1;
  89.                 left = new T[mid];
  90.                 right = new T[mid + 1];
  91.                 Array.Copy(nodes, 0, left, 0, mid);
  92.                 Array.Copy(nodes, mid + 1, right, 0, mid+1);
  93.                 foreach (T[] l in allBalancedTreeCombinations(left))
  94.                 {
  95.                     foreach (T[] r in allBalancedTreeCombinations(right))
  96.                     {
  97.                         result = new T[nodes.Length];
  98.                         result[0] = nodes[mid];
  99.                         foreach (T[] a in allMergeCombinations(l, r))
  100.                         {
  101.                             Array.Copy(a, 0, result, 1, a.Length);
  102.                             yield return result;
  103.                         }
  104.                     }
  105.                 }
  106.  
  107.  
  108.             }
  109.         }
  110.  
  111.         public IEnumerable<T[]> allMergeCombinations(T[] firstArray, T[] secondArray)
  112.         {
  113.             if (firstArray.Length == 0)
  114.             {
  115.                 yield return secondArray;
  116.             }
  117.             else if (secondArray.Length == 0)
  118.             {
  119.                 yield return firstArray;
  120.             }
  121.             else
  122.             {
  123.                 T[] result;
  124.  
  125.                 T[] firstMinusOne;
  126.                 firstMinusOne = new T[firstArray.Length - 1];
  127.                 Array.Copy(firstArray, 1, firstMinusOne, 0, firstMinusOne.Length);
  128.                 foreach (T[] a in allMergeCombinations(firstMinusOne, secondArray))
  129.                 {
  130.                     result = new T[firstArray.Length + secondArray.Length];
  131.                     result[0] = firstArray[0];
  132.                     Array.Copy(a, 0, result, 1, a.Length);
  133.                     yield return result;
  134.                 }
  135.  
  136.                 T[] secondMinusOne;
  137.                 secondMinusOne = new T[secondArray.Length - 1];
  138.                 Array.Copy(secondArray, 1, secondMinusOne, 0, secondMinusOne.Length);
  139.                 foreach (T[] a in allMergeCombinations(firstArray, secondMinusOne))
  140.                 {
  141.                     result = new T[firstArray.Length + secondArray.Length];
  142.                     result[0] = secondArray[0];
  143.                     Array.Copy(a, 0, result, 1, a.Length);
  144.                     yield return result;
  145.                 }
  146.  
  147.             }
  148.         }
  149.     }
  150. }
  151.  
Success #stdin #stdout 0.03s 33864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
C A B D E 
C A D B E 
C A D E B 
C D A B E 
C D A E B 
C D E A B 
C A B E D 
C A E B D 
C A E D B 
C E A B D 
C E A D B 
C E D A B 
C B A D E 
C B D A E 
C B D E A 
C D B A E 
C D B E A 
C D E B A 
C B A E D 
C B E A D 
C B E D A 
C E B A D 
C E B D A 
C E D B A
https://ideone.com/NBQu7c
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!