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:
12 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!