// Copyright (C) 2005 Peter Luschny
// All rights reserved.
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom
// the Software is furnished to do so, subject to the following
// conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// Comments and bug reports are welcome.
// Mailto: peter(at)luschny.de
// Author: Peter Luschny, 2005-01-05
//
// -----------------------------------------------------------------------
// Purpose: To generate and count all complete rulers.
//
// Let us call a nonnegative integer m a 'mark'. A ruler R is a strict
// increasing finite sequence of marks. By convention the first mark is 0.
//
// The number of marks of the ruler R will be denoted by M(R) and the
// distance (i.e. absolute difference) between the last and the first
// mark is the length of the ruler L(R). A segment of a ruler is the space
// between two adjacent marks; a ruler with M marks has S = M - 1 segments.
//
// The set of all distances a ruler can measure is
// D(R) = { d | d = |m' - m''|  with m' =/= m'' in R }
//
// We call a ruler R 'complete' iff D(R) = {1,2,3,...,n} for some integer n.
// In other words, given a distance d with 1 <= d <= L(R)  we can find 
// two marks m and m', such that m < m' and d = m' - m.
// More information about complete rulers can be found at:
// http://www.luschny.de/math/rulers/prulers.html
// See also: On-Line Encyclopedia of Integer Sequences A103293..A103303
//
// This implementation is kept as simple as possible, combining
// two off-the-shelf algorithms, D.E. Knuth, TAOCP 4, 7.2.1.4,
// Algorithm H and TAOCP 4, 7.2.1.2, Algorithm L. The result is
// an 'exact' algorithm for generating complete rulers.
// -----------------------------------------------------------------------

using System;

namespace Ruler
{
  class CompleteRulers
  {
    static void Main(string[] args)
    {
      int length = 7, segments = 4;
      bool print = true;

      Console.WriteLine("CompleteRulers");

      CompleteRulers R = new CompleteRulers(length, segments, print);

      R.PrintResults();
      R.PrintTriangel(16);

      Console.ReadLine();
    }

    private readonly int L, S;
    private long H_Count, P_Count, R_Count;
    private int[] a, p;

    bool print = true, printType = false;

    /// Generates all complete rulers
    /// with lenght L and S segments (S+1 marks).
    CompleteRulers(int l, int s, bool doprint)
    {
      print = doprint;

      L = l; S = s;
      a = new int[s + 2];
      p = new int[s + 1];
      Hindenburg(l, s);
    }

    /// Generating Integer-Partitions of n into m parts.
    /// D.E. Knuth, TAOCP 4, 7.2.1.4, Algorithm H
    void Hindenburg(int n, int m)
    {
      if(n < 2 || m < 2 || n < m)
      {
        throw new System.ArgumentOutOfRangeException();
      }

      H_Count = 0;

      for (int k = 2; k <= m; k++) { a[k] = 1; }
      a[m+1] = -1;

      int s = n - m + 1;

      while(true)
      {
        if(a[S] > 1) return; // Speed-Up for rulers

        a[1] = s;
        H_Visit();

        while(a[2] < a[1] - 1)
        {
          a[1]--; a[2]++;
          H_Visit();
        }

        s = a[1] + a[2] - 1;
        int j = 3;

        while(a[j] >= a[1] - 1) { s += a[j++]; }

        if(j > m) return;

        int x = a[j] + 1;
        a[j--] = x;

        while(j > 1)
        {
          a[j--] = x;
          s -= x;
        }
      }
    }

    /// Visit-point of the Hindenburg-enumeration
    /// Unfortunatly 'Hindenburg' generates in
    /// colex order, 'Pandita' requires lex order
    /// so we have to reflect.
    void H_Visit()
    {
      // PrintPartition(a);

      int m = 1;
      p[0] = 0;
      for(int k = S; k > 0; k--)
      {
        p[m++] = a[k];
      }

      H_Count++;
      Pandita();
    }

    /// Generates Permutations of the sequence p.
    /// D.E. Knuth, TAOCP 4, 7.2.1.2, Algorithm L
    void Pandita()
    {
      int s = S;

      while(true)
      {
        if(p[1] != 1) return; // SpeedUp for rulers

        P_Visit();

        int j = s - 1;
        while(p[j] >= p[j+1]) --j;

        if(j == 0) return;

        int l = s;
        while(p[j] >= p[l]) --l;

        int x = p[j]; p[j] = p[l]; p[l] = x;

        l = s + 1;
        while(++j < --l)
        {
          x = p[j]; p[j] = p[l]; p[l] = x;
        }
      }
    }

    /// Visit-point of the Pandita-enumeration.
    void P_Visit()
    {
      P_Count++;
      R_Visit();
    }

    /// Visit-point for the ruler.
    /// We test the ruler: Is it complete?
    void R_Visit()
    {
      int[] d = new int[L + 1];

      for(int i = 1; i < p.Length;  i++)
      {
        int s = 0;
        for(int j = i; j < p.Length; j++)
        {
          s += p[j];
          d[s]++;
        }
      }

      int t = 0;
      for (int i = 1; i < d.Length; i++)
      {
        if(d[i] != 0) t++; else break;
      }

      if(t == L)
      {
        R_Count++;
        if(print)
        {
          if( printType ) PrintType(d);
          PrintRuler(true);
        }

        if(p[S] != 1)
        {
          R_Count++;
          if(print) { PrintRuler(false); }
        }
      }
    }

    //-- Some functions for formatted output ----

    /// Prints the ruler.
    void PrintRuler(bool forward)
    {
      int s = 0;

      Console.Write("[0");

      if(forward)
      {
        for (int i = 1; i < p.Length; i++)
        {
          s += p[i]; Console.Write(",{0}", s);
        }
      }
      else
      {
        for (int i = p.Length - 1; i > 0; i--)
        {
          s += p[i]; Console.Write(",{0}", s);
        }
      }

      Console.WriteLine("]");
    }

    void PrintPartition(int[] a)
    {
      Console.Write("P  ");
      for(int i = 1; i < a.Length-1; i++)
      {
        Console.Write("{0},", a[i]);
      }
      Console.WriteLine();
    }

    void PrintType(int[] t)
    {
      Console.Write(" Type: ");
      for (int i = 1; i < t.Length; i++)
      {
        if( t[i] != 1)
          Console.Write("{0}^{1},", i, t[i]);
      }
      Console.WriteLine();
    }

    public void PrintResults()
    {
      Console.WriteLine();
      Console.WriteLine("Input: Length= {0}, Segments= {1}", L, S);
      Console.WriteLine("Partitions {0} Permutations {1} Rulers {2}",
        H_Count, P_Count, R_Count);
      Console.WriteLine();
    }

    public void PrintTriangel(int len)
    {
      for (int n = 2; n < len; n++)
      {
        for(int s = 2; s <= n; s++)
        {
          CompleteRulers r = new CompleteRulers(n, s, false);
          Console.Write("{0},", r.R_Count);
        }
        Console.WriteLine();
      }
    }
  }
}

// Sample output:
//
// complete Rulers
// [0,1,2,3,7]
// [0,4,5,6,7]
// [0,1,2,4,7]
// [0,3,5,6,7]
// [0,1,2,5,7]
// [0,2,5,6,7]
// [0,1,3,6,7]
// [0,1,4,5,7]
// [0,2,3,6,7]
// [0,1,4,6,7]
// [0,1,3,5,7]
// [0,2,4,6,7]
//
// Input: Length= 7, Segments= 4
// Partitions 3 Permutations 10 Rulers 12
//
// 1,
// 2,1,
// 0,3,1,
// 0,4,4,1,
// 0,2,9,5,1,
// 0,0,12,14,6,1,
// 0,0,8,27,20,7,1,
// 0,0,4,40,48,27,8,1,
// 0,0,0,38,90,75,35,9,1,
// 0,0,0,30,134,166,110,44,10,1,
// 0,0,0,14,166,311,277,154,54,11,1,
// 0,0,0,6,166,490,590,431,208,65,12,1,
// 0,0,0,0,130,660,1096,1022,639,273,77,13,1,
// 0,0,0,0,80,800,1816,2132,1662,912,350,90,14,1,