// Generowanie podzbiorów zbioru n-elementowego za pomocą Kodu Grey’a.
// www.algorytm.org
// (c) 2006 Krzysztof Kwiatkowski, implementacja Java Tomasz Lubinski


public class Kod_Graya {
	
	private static int n;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] imie;
		int[] w;
		
		System.out.println("Ilosc elementow (wartosc większa od 2): "); 
		n = Console.readInt("?");
		
		if (n < 2) {
			System.out.println("Zła liczba elementów");
			return;
		}
		
		imie = new String[n];
		int[] v = new int[n];
		
		for (int i=0; i<n; i++) {
			System.out.println("Podaj imie " + (i+1));
		    imie[i] = Console.readString();
		}

		w = GenerujWektorPrzejsc(n);
		
		for (int i=0; i<n; i++)
		    v[i] = 0;
		
		for (int i=0; i<w.length; i++) {
		    if (v[w[i]-1] == 0)
		      v[w[i]-1] = 1;
		    else
		      v[w[i]-1] = 0;
		    
		    System.out.println("");
		    System.out.print((i+1) + ": ");
		    
		    for (int j=0; j<n; j++)
		        if (v[j] == 1)
		          System.out.print(imie[j] + ", ");
		}
	}
	
	/**
	 * 
	  *  Funkcja przeksztalcajaca liczbe calkowita
	  *  na zapis dwojkowy. Wynikiem jest wektor
	  *
	  *  Pierwsza liczba w zwracanym wektorze to ilosc elementow
	  *  obliczonej liczby.	 * 
	 */
	private  int[] ZmianaPodstawy2Wektor(int pods, int liczba)
	{
		int v[] = new int[n];
		int w[] = new int[n];
	    int i, j;
	    
	    if (liczba < 0) {
	      System.out.println("Liczba mniejsza od 0. Nie obsluguje");
	      return null;
	    }
	    
	    if (liczba == 0) {
	      v[0] = 1;
	      v[1] = 0;
	      return v;
	    }
	    
	    i = 0;
	    while (liczba > 0) {
	      i++;
	      v[i] = liczba % pods;
	      liczba = liczba / pods;
	    }
	    for (j=1; j<i; j++)
	    	w[j] = v[i-j+2];
	    
	    w[0] = i-1;
	    return w;
	}
	
	 /**
	  *
	  *   Ta funkcja przeszktalca liczbe z systemu o podstawie pods zapisanej
	  *   w wektorze, do liczby w systemie dziesietnym.
	  *   Podana liczba w wektorze v, musi miec specyficzna postac, tzn.
	  *   pierwszy element tablicy to liczba mowiaca ile cyfr ma liczba
	  *   do przeksztalcenia.
	  *
	  *   np. v=[3,1,1,0]; (czyli w systemie dziesietnym jest to = 6)
	  *
	  */
	  private int ZmianaPodstwy2Liczba(int pods, int[] v) {
	    int suma, i, j;
	    
	    suma = 0;
	    j = 0;
	    for (i=v[0]+1; i>1; i--) {
	        suma = (int) (suma+(v[i]*Math.pow(pods,j)));
	        j++;
	    }
	    return suma;
	  }

	  /**
	  *
	  *   Funkcja na podstawie indexu generuje slowo Grey'a
	  *
	  */
	  private int[] IndeksNaSlowoGreya(int i, int ile_m) {
	  
		int g[] = new int[ile_m];
		int h[] = new int[ile_m];
	    int j,z;
	  
	    for (j=0; j<h.length; j++) h[j] = 0;
	    
	    g = ZmianaPodstawy2Wektor(2,i);
	    if (ile_m<g[1]) {
	      System.out.println("Za mala liczba miejsc na ktorych nalezy przedstawic liczbe.");
	      System.out.println("Wychodze z funkcji.");
	      return null;
	    }

	    for (i=2; i<=g[1]+1; i++)
	    	h[ile_m-g[1]+i-1] = g[i];
	    for (i=1; i<=ile_m; i++) {
	      z = ile_m-i+1;
	      g[ile_m-i+1] = (h[z]+h[z-1]) % 2;
	    }

	    for (j=0; j<h.length; j++) h[j] = 0;
	    h[1] = ile_m;
	    for (i=2; i<=ile_m+1; i++) 
	    	h[i]=g[i-1];
	    
	    return h;
	  }


	  /**
	   *
	   *   Ta funkcja zwraca numer indeksu dla pobranego slowa Graya.
	   *
	   *   Parametry
	   *   v  [in] -  macierzy wyjsciowa zawierajaca w pierwszym elemencie
	   *              warosc ile_m oraz w ile_m kolejnych elementow
	   *              szukane slowo Grey'a
	   *
	   *   n [out] -  szukany indeks slowa Gray'a
	   *
	   */
	  private int SlowoGrayaNaIndeks(int v[]) {

	  		int b[] = new int[v.length + 1];
		    int i, j, suma;

		    b[1] = v[1];
		    for (j=v[1]+1; j>=2; j--) {
		      suma = 0;
		      for (i=j; i>=2; i--)
		        suma = suma+v[i];
		      b[j] = suma % 2;
		    }
		    return ZmianaPodstwy2Liczba(2,b);
	  }
	  
	  
	  /**
	   *
	   *   Funkcja ta generuje wektor przejsc korzystajac z tablic.
	   *   Wektor przejsc zawiera numery bitow, ktore ulegaja zmianie w generowaniu
	   *   kolejnych slow kodu Grey'a.
	   *   Podawany argument n oraz dlugosc rozpatrywanych slow w kodzie Grey'a,
	   *   maja taka sama wartosc.
	   *
	   *   n [in]     - dlugosc wektora wejsciowego
	   *   Tout [out] - wygenerowany wektor przejsc
	   *
	   *   UWAGA:
	   *   Pierwszy element w wektorze wyjsciowym zawiera dlugosc tego wygenerowanego
	   *   wektora.
	   */
	  private static int[] GenerujWektorPrzejsc(int n) {

		    int i,k,Twsk,j;
		    boolean flag;
		    int v[] = new int[n];
		    int warunekZak;

		    // inicjowanie wartosci poczatkowych
		    i = 1; 
		    Twsk = 0;
		    flag = true;
		    warunekZak = (int) (Math.pow(2,n)-1);
		    
		    int Tout[] = new int[warunekZak];

		    for (j=0; j<n; j++)
		    	v[j] = j;

		    while (flag) {
		      if (v[i]>0) {
		        Tout[Twsk] = v[i];
		        Twsk++;
		        v[i] = 0;
		        for (k=i-1; k>=1; k--)
		        	v[k] = k;
		        i = 1;
		      } else
		        i++;
		      
		      // obliczamy wartosci do polowy, poniewaz wartosci w ciagu sa takie same
		      // jak wartosci w obliczonym ciagu ale od tylu.

		      // TO DO: dla n= 2 ten program nie dziala. Powodem jest ten warunek ponizej.
		      // Powoduje on wystepowanie petli nieskonczonej
		      if (Twsk ==((warunekZak) / 2 )) 
		    	  flag = false;
		    }
		    // wartosc 2^(n-1) jest zawsze rowna n (jest to srodek ciagu, miejsce
		    // w kodzie Grey'a gdzie pierwsza wartosc kodu zmienia sie z 0 na 1)
		    Tout[Twsk] = n;

		    j = 1;
		    for (i=Twsk+1; i<warunekZak; i++) {
		      Tout[i] = Tout[Twsk-j];
		      j++;
		    }

		    return Tout;
	  }
	  

}