/*
 * Created on 03/29/2009
 * 
 * On the Prism of the Parcelatories
 * (http://www.scientificblogging.com/vastness_ways_science/prism_parcelatories)
 * 
 * Copyright (C) 2009 Eduardo Sardeiro 
 * (sardeiro@gmail.com)
 * 
 * This program is free software; you can redistribute it  and/or
 * modify it under the terms of the GNU  General  Public  License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR  A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy  of  the  GNU  General  Public 
 * License along with this  program; if not, write  to  the  Free 
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, 
 * MA  02111-1307, USA.
 * 
 * 
 * http://www.gnu.org/licenses/gpl.txt
 */
 
 
/* 
 * Criado em 29/03/2009
 *
 * Sobre o Prisma das Parcelatórias 
 * (http://stoa.usp.br/esardeiro/weblog/45842.html)
 *
 * Direitos Autorais Reservados (C) 2009 Eduardo Sardeiro 
 * (sardeiro@gmail.com)
 * 
 * Este programa é software livre; você pode redistribuí-lo  e/ou 
 * modificá-lo sob os termos da Licença Pública  Geral GNU versão 
 * 2 conforme publicada pela Free Software Foundation. 
 * 
 * Este programa é distribuído na expectativa de  que  seja  útil, 
 * porém, SEM NENHUMA GARANTIA; nem mesmo a garantia implícita de 
 * COMERCIABILIDADE OU  ADEQUAÇÃO  A  UMA  FINALIDADE  ESPECÍFICA. 
 * Consulte a Licença Pública Geral do GNU  para  mais detalhes.
 * 
 * Você deve ter recebido uma cópia da Licença  Pública  Geral do 
 * GNU versão 2 junto com este programa; se não, escreva  para  a 
 * Free Software Foundation, Inc., no  endereço 59 Temple Street, 
 * Suite 330, Boston, MA 02111-1307 USA. 
 * 
 *
 * http://www.magnux.org/doc/GPL-pt_BR.txt
 */


public class Partition {
       
       public static void Partition() {
       }
       
       /* 
        * parcelatory(number, parcels)
        * ---------------------------
        */
        
       /* 
        * This method returns the number of parcelatories of any
        * number, given the quantity of parcels.
        *
        * e.g.:
        * parcelatory(5,2) = 2  that are '1+4' and '2+3'.
        *
        */
        
       /* 
        * Este método retorna o número de parcelatórias de um 
        * número (number), dada uma quantidade de parcelas 
        * (parcels).
        *
        * Exemplo: 
        * parcelatory(5,2) = 2  que são '1+4' e '2+3'.
        *
        */
       public static long parcelatory(
              long number,
              long parcels) {
              
              long r = 0;
              
              if (number < parcels) {
                 r = 0;
              }   
              else if (number == parcels) {
                 r = 1;
              }
              else if (parcels == 1) {
                 r = 1;
              }
              else {
                 r = parcelatory(number - 1, parcels - 1) +
                     parcelatory(number - parcels, parcels);
              };
          
              return r;
       }
       
       /* 
        * parcelatoryOfEuler(number, parcels)
        * ----------------------------------
        */
        
       /* 
        * This method returns the number of extended parcelatories
        * of any number, given the quantity of parcels.
        *
        * e.g.:
        * parcelatoryOfEuler(5,2) = 4  that are '1+4','2+3', '3+2' and '4+1'.
        *
        */
       
       /*
        * Este método retorna o número de parcelatórias extendidas
        * de um número (number), dada uma quantidade de parcelas 
        * (parcels).
        * 
        * Exemplo: 
        * parcelatoryOfEuler(5,2) = 4  que são '1+4','2+3', '3+2' e '4+1'.
        *
        */
       public static long parcelatoryOfEuler(
              long number,
              long parcels) {
              
              long r = 0;
              
              if (number < parcels) {
                 r = 0;
              }
              else if (number == parcels) {
                 r = 1;
              }
              else if (parcels == 1) {
                 r = 1;
              }
              else {
                 r = parcelatoryOfEuler(number - 1, parcels - 1) +
                     parcelatoryOfEuler(number - 1, parcels);
              };
          
              return r;
       }
       
       /* 
        * count(number, parcels, sequence)
        * --------------------------------
        */
        
       /* 
        * This method returns the n-th count (sequence) of the normal 
        * Parcelatory (no-Eulerian) of any number, given the quantity 
        * of parcels and its sequence.
        *
        * e.g.:
        * count(5,2,1) = '1+4';
        * count(5,2,2) = '2+3'.
        *
        */
        
       /* 
        * Este método retorna a n-ésima conta (sequence) da Parcelatoria
        * normal (não Euliana) de um número (number) dada uma quantidade 
        * de parcelas (parcels) e sua sequência.
        *
        * Exemplos: 
        * count(5,2,1) = '1+4';
        * count(5,2,2) = '2+3'.
        *
        */
       public static String count(
              long number,
              long parcels,
              long sequence) {
              
              return count(number, parcels, sequence, 0);
       }
       
       /* 
        * count(number, parcels, sequence, additional)
        * -------------------------------------------
        */
        
       /* 
        * Internal call of the count() method.
        */
        
       /* 
        * Chamada interna do método count().
        *
        */
       private static String count(
               long number,
               long parcels,
               long sequence,
               long additional) {
               
               long f;
               long i;
               long t;
               
               String r = "";
               
               if (sequence < 1 || sequence > parcelatory(number, parcels)) {
                  r = "";
               }
               else {
                  if (number < parcels) {
                     r = "";
                  }
                  else if (parcels == 1) {
                     r = "" + (number + additional);
                  }
                  else {
                     i = sequence;
                     f = parcelatory(number - 1, parcels - 1);
                     
                     if (i <= f) {
                        r = "" + (1 + additional) + "+" + count(number - 1, parcels - 1, i, additional);
                     }
                     else {
                        r = count(number - parcels, parcels, i - f, 1 + additional);
                     };
                  };
               }; 
               
               return r;
       }
       
       /* 
        * parcel(number, parcels, sequence, nparcel)
        * ------------------------------------------
        */
        
       /* 
        * This method returns the n-th parcel (nparcel) of n-th count 
        * (sequence) of the normal Parcelatory (no-Eulerian) of any 
        * number, given the quantity of parcels and its sequence.
        *
        * e.g.:
        * count(5,2,1) = '1+4', so
        * parcel(5,2,1,1) = '1' and
        * parcel(5,2,1,2) = '4'.
        *        
        * count(5,2,2) = '2+3', so
        * parcel(5,2,2,1) = '2' and
        * parcel(5,2,2,2) = '3'.
        *
        */
        
       /* 
        * Este método retorna a n-ésima parcela (nparcel), da m-ésima 
        * conta (sequence) da Parcelatoria normal (não Euliana) de um 
        * número (number) dada uma quantidade de parcelas (parcels) e 
        * sua sequencia.
        *
        * Exemplos: 
        * parcel(5,2,1) = '1+4', então:
        * parcel(5,2,1,1) = '1' e
        * parcel(5,2,1,2) = '4'.
        *        
        * parcel(5,2,2) = '2+3', então:
        * parcel(5,2,2,1) = '2' e
        * parcel(5,2,2,2) = '3'.
        *
        */
       
       public static long parcel(
              long number,
              long parcels,
              long sequence,
              long nparcel) {
              
              return parcel(number, parcels, sequence, nparcel, 1, 0);
       }
       
       /* 
        * parcel(number, parcels, sequence, nparcel, additional)
        * ------------------------------------------------------
        */
        
       /* 
        * Internal call of the parcel() method.
        */
        
       /* 
        * Chamada interna do método parcel()
        *
        */
       
       private static long parcel(
               long number,
               long parcels,
               long sequence,
               long nparcel,
               long pos,
               long additional) {
               
               long a;
               
               long i;
               long q;
               long t;
               
               long r = 0;
               
               q = parcelatory(number, parcels);
               
               if (sequence < 1 || sequence > q) {
                  r = 0;
               }
               else {
                  if (number < parcels) {
                     r = 0;
                  }
                  else if (parcels == 1) {
                     if (nparcel == pos) {
                        r = number + additional;
                     };
                  }
                  else {
                     i = sequence;
                     q = parcelatory(number - 1, parcels - 1);
                     
                     if (i <= q) {
                        if (nparcel == pos) {
                           r = 1 + additional;
                        }
                        else {
                           r = parcel(number - 1, parcels -1, i, nparcel, pos + 1, additional);
                        };
                     }
                     else {
                        r = parcel(number - parcels, parcels, i - q, nparcel, pos, 1 + additional);
                     };
                  };
               }; 
               
               return r;
       }
}