Oppgave 1

Hvis gjennomsnittet for de 3ⁿ forskjellige permutasjonene er 2n/3, vil det det sammenlagte antallet ombyttinger for de 3ⁿ permutasjonene bli lik  (2n/3)3ⁿ = 2n*3^n-1. For n = 4, 5 og 6 blir det henholdsvis 216, 810 og 2916.

Hvis en bruker "RRRR" (fire R-er) i Programkode 1.3.10 f), vil en få sjekket resultatet for n = 4. Ved å øke antall R-er, får en sjekket n = 5 og 6.

Oppgave 2

  public static void omorganiser(char[] c, char x, char y, char z)
  {
    int v = 0, h = c.length-1, k = h;       // v forrest, h og k bakerst
    while (v <= h)
    {
      if (c[h] == x) Tabell.bytt(c,v++,h);
      else if (c[h] == y) h--;
      else  Tabell.bytt(c,h--,k--);
    }
  }

  public static boolean nestePermutasjon(char[] c, char x, char y, char z)
  {
    int n = c.length, i = n - 1;        // i starter bakerst i c

    while (i >= 0 && c[i] == z) i--;
    if (i < 0) return false;            // tabellen c har kun z-er

    c[i] = (c[i] == x ? y : z);
    for (int j = i+1; j < n; j++) c[j] = x;

    return true;  // c inneholder en ny permutasjon
  }

  public static int antallOmorganiser(char[] c, char x, char y, char z)
  {
    int v = 0, h = c.length-1, k = h;  // v forrest, h og k bakerst

    int antall = 0;  // antall ombyttinger

    while (v <= h)
    {
      if (c[h] == x) { Tabell.bytt(c,v++,h); antall++; }
      else if (c[h] == y) h--;
      else  { Tabell.bytt(c,h--,k--); antall++; }
    }
    return antall;
  }

  public static void main(String ... args)   // hovedprogram
  {
    char[] c = "RRRR".toCharArray(), d = new char[c.length];
    boolean flere = true; int antall = 0;  // antall ombyttinger

    while (flere)
    {
      System.arraycopy(c,0,d,0,c.length);  // kopierer c over i d
      antall += antallOmorganiser(d,'R','H','B');      // omorganiserer d
      flere =  nestePermutasjon(c,'R','H','B');        // ny permutasjon
    }

    System.out.println(antall);            // Utskrift: 216
  } 

Oppgave 3

  public static int antallOmorganiser(char[] c)
  {
    int v = 0, h = c.length-1, k = h;  // v forrest, h og k bakerst

    int antall = 0;  // antall ombyttinger

    while (v < h)
    {
      if (c[h] == 'R')
      {
        Tabell.bytt(c, v++, h);
        antall++;
      }
      else if (c[h] == 'H') h--;
      else // nå er c[h] == 'B'
      {
        if (h != k)
        {
          Tabell.bytt(c,h,k);
          antall++;
        }
        h--; k--;
      }
    }
    // nå er v == h
    if (c[h] == 'B' && h != k)
    {
      Tabell.bytt(c, h, k);
      antall++;
    }

    return antall;
  } 

Oppgave 4

  public static void parter(int[] a, int s1, int s2)
  {
    // skilleverdiene s1 og s2 må oppfylle s1 <= s2
    if (s1 > s2)
      throw new IllegalArgumentException("s1 > s2");

    int v = 0, h = a.length-1, k = h;

    while (v <= h)
    {
      if (a[h] < s1) Tabell.bytt(a, v++, h);
      else if (a[h] < s2) h--;
      else Tabell.bytt(a,h--,k--);
    }
  }

Oppgave 5

  // Her brukes samme idé som i Programkode 1.3.10 b).
  // Antall ombyttinger kan reduseres litt hvis vi fjerner
  // de tilfellene der et element byttes med seg selv.

  public static void mauritius(char[] c)
  {
    // Tabellen holdes femdelt - først R-ene,
    // så den ukjente delen, så B-ene, så Y-ene
    // og til slutt G-ene.

    int v = 0, h = c.length-1, k = h, m = h;

    // v skal være forrest og h sist i den ukjente
    // delen, k bakerst i B-ene og m bakerst i Y-ene

    while (v <= h)
    {
      char d = c[h];
      if (d == 'R') Tabell.bytt(c,v++,h);
      else if (d == 'B') h--;
      else if (d == 'Y') Tabell.bytt(c,h--,k--);
      else  // d == 'G'
      {
        c[h] = c[k]; c[k] = c[m]; c[m] = d;
        h--; k--; m--;
      }
    }
  }