// L?sningsforslag, Inf110 oppgaver, uke 3

// Oppgave 1: T?rnene i Hanoi

public class Hanoi {
    static int antallFlytt = 0;

    /* Parameter til programmet: antall ringer som skal flyttes */
    public static void main(String[] args) {
        int antallRinger = Integer.parseInt(args[0]);

	/* Skal flytte alle ringene fra pinne 1 til pinne 3
     * via pinne 2.
     */
	flytt(antallRinger, 1, 3, 2);

	System.out.println("Antall flytt: " + antallFlytt);
    }

    /* Skal flytte ant ringer fra fra-pinnen til til-pinnen ved hjelp
     * av via-pinnen. Dette skjer rekursivt etter f?lgende m?nster:
     * 1) Flytt alle ringene unntatt den nederste fra fra-pinnen
     *    til via-pinnen.
     * 2) Flytt den nederste ringen til til-pinnen.
     * 3) Flytt alle ringene fra punkt 1 over p? til-pinnen
     */
    public static void flytt(int ant, int fra, int til, int via) {
	if (ant == 1) {
	    flytt1(fra, til);
	} else {
	    flytt(ant - 1, fra, via, til);
	    flytt1(fra, til);
	    flytt(ant - 1, via, til, fra);
	}
    }

    /* Her skjer selve flyttingen av hver enkelt ring */
    public static void flytt1(int fra, int til) {
	antallFlytt++;
	System.out.println("Fra: " + fra + " Til: " + til);
    }
}

/*
Hvor mange trekk blir det om man skal flytte N ringer?
     2**N - 1

2**64 - 1 = 18 446 744 073 709 551 615
Dvs:
If the priest of the Tower of Brahma can make one transfer
every second, they must work more than 500 000 million years.
We can rest easy. The end of the world will not come tomorrow.

Resultat av kj?ringer:
Hanoi 3
Fra: 1 Til: 3
Fra: 1 Til: 2
Fra: 3 Til: 2
Fra: 1 Til: 3
Fra: 2 Til: 1
Fra: 2 Til: 3
Fra: 1 Til: 3
Antall flytt: 7

Hanoi 4
Fra: 1 Til: 2
Fra: 1 Til: 3
Fra: 2 Til: 3
Fra: 1 Til: 2
Fra: 3 Til: 1
Fra: 3 Til: 2
Fra: 1 Til: 2
Fra: 1 Til: 3
Fra: 2 Til: 3
Fra: 2 Til: 1
Fra: 3 Til: 1
Fra: 2 Til: 3
Fra: 1 Til: 2
Fra: 1 Til: 3
Fra: 2 Til: 3
Antall flytt: 15
*/


//////////////////////////////////////////////////////////////////////////
// Oppgave 2: Avslutning av rekursjon

// Studentene er ikke bedt om ? programmere. 
// F?lgende program er laget for ? telle kall og verifisere 
// formlene for antall kall for de to variantene av gen.
//  gen1 fra oppgaven
//  gen2 fra notatet Krogdahl, Maus: Kombinatorisk . .  side 9

public class AvslutningRek {
  int [] p;
  boolean [] brukt;
  int n; 
  int c1=0;  // antall kall p? gen1
  int ap1=0; // antall permutasjoner fra gen1 
  int c2=0;  // antall kall p? gen2
  int ap2=0; // antall permutasjoner fra gen2 

  public AvslutningRek(int n) {
    this.n=n;
    p=new int[n];
    brukt=new boolean[n];
    for (int j=0; j<n; j++) brukt[j]=false;
    gen1(0);
    for (int j=0; j<n; j++) brukt[j]=false;
    gen2(0);
    System.out.println("For "+n+" kalles gen1 "+c1+" ganger. Antall perm="+ap1);
    System.out.println("For "+n+" kalles gen2 "+c2+" ganger. Antall perm="+ap2);
    
    // beregn formel:
    //  1 + n + n*(n-1) + n*(n-1)*(n-2) +....+ (n*(n-1)*..*2)
    int t1=1;
    int til=1;
    for (int j=n; j>1; j--) {
      til*=j;
      t1+=til;
    }
    System.out.println("For "+n+": formel for gen1 "+(t1+til)+" ganger.");
    System.out.println("For "+n+": formel for gen2 "+t1+" ganger.");
  }

  void gen1(int i) {
    c1++;
    if (i==n) {
      // bruk perm
      ap1++;
    } else {
      for (int siff=0; siff<n; siff++) {
        if (!brukt[siff]) {
          brukt[siff]=true;
          p[i]=siff;
          gen1(i+1);
          brukt[siff]=false;
        }
      }
    }
  }

  void gen2(int i) {
    c2++;
    for (int siff=0; siff<n; siff++) {
      if (!brukt[siff]) {
        brukt[siff]=true;
        p[i]=siff;
        if (i<n-1) gen2(i+1);
        else {
          // bruk perm
          ap2++;
        }
        brukt[siff]=false;
      }
    }
  }

  public static void main(String[] args) {
    if (args.length<1) {
      System.out.println("Bruk: \n>java AvslutningRek <n>");
    } else {
      new AvslutningRek(new Integer(args[0]).intValue());
    }
  }
}

/*
  Totalt antall kall p? gen2(0): 1
Hver gen2(0) gj?r n kall p? gen2(1). 
  Totalt antall kall p? gen2(1): n
Hver gen2(1) gj?r n-1 kall p? gen2(2). 
  Totalt antall kall p? gen2(2): n*(n-1)
...
Hver gen2(i) gj?r n-i kall p? gen2(i+1). 
  Totalt antall kall p? gen2(i+1): n*(n-1)*..*(n-i)
...
Hver gen2(n-2) gj?r 2 kall p? gen2(n-1). 
  Totalt antall kall p? gen2(n-1): n*(n-1)*..*2
Hver gen2(n-1) gj?r 0 kall p? gen2(). 

Totalt antall kall p? gen2:
1 + n + n*(n-1) + n*(n-1)*(n-2) +....+ (n*(n-1)*..*2)
-----------------------------------------------------

For gen1 gjelder det samme som for gen2 bortsett for at
Hver gen1(n-1) gj?r 1 kall p? gen1(n). 
  Totalt antall kall p? gen1(n): n*(n-1)*..*2

Totalt antall kall p? gen1:
1 + n + n*(n-1) + n*(n-1)*(n-2) +....+ (n*(n-1)*..*2) + (n*(n-1)*..*2)
----------------------------------------------------------------------

Dvs. det er n! flere kall p? gen1 enn p? gen2.
Virker mye, men relativt er det mindre enn dobbelt s? mange.

Resultat av kj?ring:
For 5 kalles gen1 326 ganger. Antall perm=120
For 5 kalles gen2 206 ganger. Antall perm=120
For 5: formel for gen1 326 ganger.
For 5: formel for gen2 206 ganger.

For 10 kalles gen1 9864101 ganger. Antall perm=3628800
For 10 kalles gen2 6235301 ganger. Antall perm=3628800
For 10: formel for gen1 9864101 ganger.
For 10: formel for gen2 6235301 ganger.

*/

////////////////////////////////////////////////////////////////////////////
// Oppgave 3: Sekvens-generering

class Sekvens{
    /* Programparametre: n (lengden) og m (en mer enn st?rste tall) */
    public static void main(String[] args) {
	Array a = new Array(Integer.parseInt(args[0]),
			    Integer.parseInt(args[1]));
	a.gen(0);
    }
}

class Array{
    int n, m;
    int[] p;

    Array(int n1, int m1) {
	n = n1;
	m = m1;
	p = new int[n];
    }

    public void gen(int i) {
	for (int siff = 0; siff < m ; siff++) {

	    // Forskjell p? minst to:
	    // if (i == 0 || Math.abs(siff - p[i - 1]) >= 2) {

	    // Ikke-avtagende sekvenser:
	    // if (i == 0 || siff >= p[i - 1]) {

		p[i] = siff;
		if (i < n-1) {
		    gen(i + 1);
		} else {
		    for (int j = 0; j < n; j++) {
			System.out.print(p[j]);
		    }
		    System.out.print("\n");
		}
	    // }
	}
    }
}

////////////////////////////////////////////////////////////////////////////
// Oppgave 4: Utplukk

class Utplukk {
    int n;
    int m;
    boolean[] ermed;
    int antall;

    Utplukk(int n1, int m1) {
	n = n1;
	m = m1;
	ermed = new boolean[n];
	antall = 0;
    }

    /* Lager f?rst en metode som genererer ALLE mulige utplukk */
    void gen(int i) {
	// Alle mulige utplukk MED element i:
	ermed[i] = true;
	antall++;

	if (i == n - 1) {
	    for (int j = 0; j < n; j++) {
		if (ermed[j]) {
		    System.out.print(j);
		}
	    }
	    System.out.print("\n");
	} else {
	    gen(i + 1);
	}

	// Alle mulige utplukk UTEN element i:
	antall--;
	ermed[i] = false;

	if (i == n - 1) {
	    for (int j = 0; j < n; j++) {
		if (ermed[j]) {
		    System.out.print(j);
		}
	    }
	    System.out.print("\n");
	} else {
	    gen(i + 1);
	}
    }

    /* Endrer litt p? gen slik at vi bare f?r de utplukkene med m elementer */
    void gen2(int i) {

	ermed[i] = true;
	antall++;

	// Ny test: Skriver ut hvis vi n? har oppn?dd m elementer
	if (antall == m) {
	    for (int j = 0; j < n; j++) {
		if (ermed[j]) {
		    System.out.print(j);
		}
	    }
	    System.out.print("\n");
	} else {
	    gen2(i + 1);   // NB! Trenger ingen ekstra test her!
	}

	// Alle mulige utplukk UTEN element i:
	antall--;
	ermed[i] = false;

	// Skal bare kalle videre hvis det er h?p om ? f? m elementer
	if (antall + (n - 1 - i) >= m) {
	    gen2(i + 1);
	}
    }
}

////////////////////////////////////////////////////////////////////////////
/* Oppgave 5: Beregning av polynomer

2.13 a)  
En algoritme hvor x**i beregnes i en for-l?kke har orden N**2

2.13 b)
En algoritme hvor x**i beregnes ved pow(x,i) fra MAW side 46 har orden NlogN

2.14 a)
x=3
n=4
a[] = 2  1  0  8  4

poly 0   4   20   60   181   543
 - - - - - - - - - - - - - - - - - - - - - - - - - >
i      4   3    2    1     0

2.14 b)
La 0 <= j <= N.
N?r i i for-l?kka kommer til j vil a[j] bli lagt til poly.
Det er da igjen j oml?p i l?kka. For hvert oml?p vil
a[j]-biten av poly multipliseres med x.
Til slutt vil a[j] bidra med a[j]*(x**j) til totalen.

2.14 c
Algoritmen har orden N.