// 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.