Kombinacje z powtórzeniami z uwzgl. ważności elementów


(Jedras121) #1

Witam.

Potrzebny jest mi algorytm generowania kombinacji składający się z dwóch części:

  1. Jako alfabet będzie podawana tablica/lista, gdzie każdy symbol będzie miał przypisany priorytet. Priorytet określa, który symbol powinien być najpierw brany pod uwagę. Najwyższy priorytet to 1. Np.

    Alfabet: [a,1], [b,3], [c,2], [d,4]

    Wygenerowane kombinacje z uwzględnieniem priorytetów dla długości kombinacji = 1: a, c, b, d

    Wygenerowane kombinacje z uwzględnieniem priorytetów dla długości kombinacji = 2: aa, ac, ab, ad, ca, cc, cb, cd, ba, bc, bb, bd, da, dc, db, dd

Prawie udało mi się to zrobić, tylko wypisuje mi kombinacje jakby od końca. Gdzieś zrobiłem błąd w pętlach tylko nie widzę gdzie. Może ktoś zauważy to problem będzie rozwiązany. Tak wyglądają wyniki dla jasności:

[a, a, a]

[c, a, a]

[b, a, a]

[d, a, a]

[a, c, a]

[c, c, a]

[b, c, a]

...

Przed generowaniem kombinacji sortuje alfabet wg priorytetów. Kod źródłowy moich wypocin załączam na końcu. 2. Druga część jest przynajmniej wg mnie zdecydowanie trudniejsza i tu się muszę przyznać, że do niczego konstruktywnego nie doszedłem. Chodzi o to aby funkcja/metoda, która generuje kombinacje, przyjmowała na wejście: - kombinację od której zacząć generowanie - liczbę kombinację, które należy wygenerować. Czyli dla drugiego przykładu z punktu 1, będzie to wyglądać tak:generuj("ab", 5);Wynik: ad, ca, cc, cb, cd A dla generuj("dc",10); Wynik: db, dd, aaa, aac, aab, aad, aca, acc, acb, acd Uprzedzając możliwe pytanie: interesuję mnie zarówno pseudokod, jak i konkretna implementacja. Moje wypociny:

public class CombinationsWithPriority {


	private String[] array;

	private int n;


	public CombinationsWithPriority(List list, int n) {

		Collections.sort(list, new CustomComparator());

		this.array = getArray(list);

		this.n = n;

	}


	public List getVariations() {

		int l = array.length;

		int permutations = (int) Math.pow(l, n);

		String[][] table = new String[permutations][n];

		for (int x = 0; x < n; x++) {

			int t2 = (int) Math.pow(l, x);

			for (int p1 = 0; p1 < permutations;) {

				for (int al = 0; al < l; al++) {

					for (int p2 = 0; p2 < t2; p2++) {

						table[p1][x] = array[al];

						p1++;

					}

				}

			}

		}


		List result = new ArrayList<>();

		for (String[] permutation : table) {

			result.add(permutation);

		}

		return result;

	}


	public String[] getArray(List list) {

		String[] t = new String[list.size()];

		for (int i = 0; i < list.size(); i++) {

			t[i] = list.get(i).getX();

		}

		return t;

	}


	class CustomComparator implements Comparator {

		@Override

		public int compare(ListObject o1, ListObject o2) {

			return o1.getPriority().compareTo(o2.getPriority());

		}

	}


}

public class ListObject {

	private String x;

	private Integer priority;


	public ListObject(String x, int priority) {

		this.x = x;

		this.priority = priority;

	}


	public String getX() {

		return x;

	}


	public void setX(String x) {

		this.x = x;

	}


	public Integer getPriority() {

		return priority;

	}


	public void setPriority(int priority) {

		this.priority = priority;

	}


}

public class MainClass {

	public static void main(String[] args) {

		List list = new ArrayList<>();

		list.add(new ListObject("a", 1));

		list.add(new ListObject("b", 3));

		list.add(new ListObject("c", 2));

		list.add(new ListObject("d", 4));


		CombinationsWithPriority gen2 = new CombinationsWithPriority(list, 3);

		List v2 = gen2.getVariations();

		for (String[] s : v2) {

			System.out.println(Arrays.toString(s));

		}

		System.out.println("Liczba permutacji: " + v2.size());

	}

}

(Grzelix) #2

Napisałeś że pseudokod będzie również ok, więc postaram się przedstawić jak ja widzę rozwiązanie tego problemu.

  1. Wczytujesz dane i sortujesz je względem priorytetu. Dzięki temu mamy taką kolekcję (dane z przykładu)

    { "a", "c", "b","d" }

  2. Tworzysz np Listę która będzie przetrzymywać dane dla danej iteracji a dokładnie jak wygląda ciąg w danej iteracji.

Przykład: iteracja 1 długość 2: {0,0} czyli aa

iteracja 2 długość 2: {1,0} czyli ac

iteracja 3 długość 2: {2,0} czyli ab

iteracja 4 długość 2: {3,0} czyli ad

iteracja 5 długość 2: {0,1} czyli ca

tutaj jedyną trudniejszą metodą będzie ta incrementująca wartości w liście, ale łatwo zauważyć jak ona działa (plus rozszerzenie tej listy).

A wypisanie to tylko pobranie wartości z kolekcji z odpowiednich indeksów.

i jak się to ma do drugiej części. Otóż czytając słowo możemy ustalić jak lista pozycji wygląda.


(Tomek Matz) #3

Wrzucony przez Ciebie kod jedynie przejrzałem. Nie szukałem w nim błędu (lenistwo :P). Co się w nim rzuca w oczy to to, że do konstruktora klasy odpowiedzialnej za generowanie string-ów powinieneś przekazywać jedynie tablicę znaków (alfabet). To n (czyli długość kombinacji) przekazuj jako parametr metody odpowiedzialnej za generowanie string-ów.

Napisałem programik, który realizuje punkty 1 i 2 (nie robiłem sortowania wg priorytetów; założyłem sobie, że dane są już posortowane). Zrobiłem to jednak w języku C# (przy okazji ... następnym razem w tytule wiadomości podawaj o jaki język chodzi). Java jest bardzo podobna do C# więc nie powinieneś mieć problemów z czytaniem kodu (tym bardziej, że nie używałem żadnych zagmatwanych konstrukcji). Tutaj możesz zobaczyć rezultat działania programu http://ideone.com/NU1PG, a tutaj masz kod:

using System;

using System.Collections.Generic;


class Program

{

    private static char[] arr = new char[] { 'a', 'c', 'b', 'd' };


    private static Dictionary dic = new Dictionary() 

    {

        { 'a', 0 }, { 'c', 1 }, { 'b', 2 }, { 'd', 3 }

    };


    static void Main(string[] args)

    {

        Console.WriteLine("Example no 1:");

        Display(Generate(1));

        Console.WriteLine();


        Console.WriteLine("Example no 2:");

        Display(Generate(2));

        Console.WriteLine();


        Console.WriteLine("Example no 3:");

        Display(Generate("ab", 5));

        Console.WriteLine();


        Console.WriteLine("Example no 4:");

        Display(Generate("dc", 10));

        Console.WriteLine();


        Console.WriteLine("Example no 5:");

        Display(Generate("ab", 0));

        Console.WriteLine();


        Console.WriteLine("Example no 6:");

        Display(Generate(3));

        Console.WriteLine();


        Console.ReadKey();

    }


    public static void Display(List list)

    {

        list.ForEach(i => Console.Write("{0} ", i));

    }


    public static List Generate(int length)

    {

        char[] seed = new char[length];

        for (int i = 0; i < length; i++)

            seed[i] = arr[0];


        int count = -1;

        checked { count = (int)Math.Pow(arr.Length, length); }


        return Generate(new string(seed), count, true);

    }


    public static List Generate(string seed, int count)

    {

        return Generate(seed, count, false);

    }


    private static List Generate(string seed, int count, bool includeSeed)

    {

        List result = new List();

        if (includeSeed)

            result.Add(seed);


        if (result.Count < count)

            Generate(seed.ToCharArray(), result, count);


        return result;

    }


    private static void Generate(char[] previous, List result, int count)

    {

        char[] current = new char[previous.Length + 1];


        bool copy = false;

        for (int i = previous.Length - 1; i >= 0; i--)

        {

            if (copy)

                current[i + 1] = previous[i];

            else

            {

                int index = dic[previous[i]];


                if (index < arr.Length - 1)

                {

                    current[i + 1] = arr[index + 1];

                    copy = true;

                }

                else

                    current[i + 1] = arr[0];

            }

        }


        if (copy)

            result.Add(new string(current, 1, current.Length - 1));

        else

        {

            current[0] = arr[0];

            result.Add(new string(current));

        }


        if (result.Count < count)

            Generate(result[result.Count - 1].ToCharArray(), result, count);

    }

}

Jakbyś miał jakiś problem z konwersją na Javę, to daj znać. Przysiądę i Ci to zrobię (choć przyznam, że w Javie już dawno nic nie pisałem :P).


(Krystian Rosinski) #4

Nie ma wymagań co do języka, więc pozwolę sobie naszkicować rozwiązanie w Pythonie. Na wejściu prosi się o słownik, więc przyjmę jako dane, np.

abcd = {"a": 1, "b": 3, "c": 2, "d": 4}

Następnie posortuję słownik względem wartości:

abcd_sorted = sorted(abcd.items(), key=lambda x: x[1])

W rezultacie otrzymuję:

[('a', 1), ('c', 2), ('b', 3), ('d', 4)]

Następnie skorzystam z funkcji product() modułu itertools.

list(product([abcd_sorted[x][0] for x in range(len(abcd_sorted))], repeat=2))

i jako wynik dostaję listę:

[('a', 'a'), ('a', 'c'), ('a', 'b'), ('a', 'd'), ('c', 'a'), ('c', 'c'), ('c', 'b'), ('c', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'b'), ('b', 'd'), ('d', 'a'), ('d', 'c'), ('d', 'b'), ('d', 'd')]

Cała "trudność" polega na wykorzystaniu funkcji product(), której implementacja znajduje się pod wskazanym linkiem.

Podobnie drugą część pytania można sprowadzić do użycia funkcji dropwhile() i takewhile() z tego samego modułu. Implementacje wszystkich tych funkcji znajdują się na stronie, do której prowadzą linki.