// Fordeling av leketøy til barn

import java.util.Random;

public class uke_7_5
{
    int n;           // Antall barn og antall leketøy    
    int p[];         // Permutasjonsvektor som skal inneholde
                     // en fordeling av leketøy til barna
    boolean brukt[]; // Merker av utdelte leketøy

    int antOnsker[]; // Antall ønsker for hvert barn
    int onske[][];   // Ønskelistene for hvert barn
    boolean ferdig;  // true når én fordeling er funnet
	
    void delUt(int barn)
    {
	// Prøver å finne en fordeling av leker slik at alle får 
	// noe som står på ønskelisten

	if (barn == n)
	{
	    // Laget ferdig en fordeling, avslutter
	    ferdig = true;
	}
	else
	{
	    // Prøver å gi dette barnet en av lekene på
	    // ønskelisten, deler deretter ut til resten av
	    // barna rekursivt

	    for (int i = 0; i < antOnsker[barn]; i++)
	    {
		if (!brukt[onske[barn][i]])
		{
		    p[barn] = onske[barn][i];
		    brukt[onske[barn][i]] = true;
 
		    delUt(barn + 1);
		      
		    if (ferdig)
			return;

		    brukt[onske[barn][i]] = false;
		}
	    }
	}
    }

    void test()
    {
	// Testprogram som setter opp tllfeldig ønskeliste for 10
	// barn og prøver å finne en fordeling av leketøy
	    
	n = 10;
	p = new int[n];
	antOnsker = new int[n];
	onske = new int[n][n];
	ferdig = false;
	brukt = new boolean[n];
	for (int i = 0; i < n; i++)
	    brukt[i] = false;
	    
	// Alle barna ønsker seg 3 leker
	for (int barn = 0; barn < n; barn++)
	    antOnsker[barn] = 3;

	// Lager tilfeldige ønskelister for hvert barn
	Random R = new Random();
	boolean ulikeOnsker;
	for (int barn = 0; barn < n; barn++)
	    do
	    {
		// Trekker tilfeldig ønskene til dette barnet
		for (int i = 0; i < antOnsker[barn]; i++)
		    onske[barn][i] = R.nextInt(n);
		
		// Sikrer at alle ønskene til et barn er ulike
		ulikeOnsker = true;
		for (int i = 0; i < antOnsker[barn] - 1; i++)
		    for (int j = i + 1; j < antOnsker[barn]; j++)
			if (onske[barn][i] == onske[barn][j])
				ulikeOnsker = false;
	    } while (!ulikeOnsker);

	// Skriv ut ønskelistene
	System.out.println("Ønskelister: ");
	for (int barn = 0; barn < n; barn++)
	{
	    System.out.print(barn + ": ");
	    for (int j = 0; j < antOnsker[barn]; j++)
		System.out.print(onske[barn][j] + " ");
	    System.out.println();
	}

	// Finn og skriv ut fordeling av leker

	delUt(0);
	
	if (ferdig)
	{
	    System.out.println("\nFordeling: ");
	    for (int barn = 0; barn < n; barn++)
		System.out.println(barn +": " + p[barn]);
	}
	else
	    System.out.println("\nKlarer ikke å oppfylle alle ønskene");
    }


    public static void main(String args[])
    {
	uke_7_5 L = new uke_7_5();
	L.test();
    }
}