Witam.
Potrzebny jest mi algorytm generowania kombinacji składający się z dwóch części:
- 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.
- 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<ListObject> list, int n) {
Collections.sort(list, new CustomComparator());
this.array = getArray(list);
this.n = n;
}
public List<String[]> 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<String[]> result = new ArrayList<>();
for (String[] permutation : table) {
result.add(permutation);
}
return result;
}
public String[] getArray(List<ListObject> 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<ListObject> {
@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<ListObject> 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<String[]> v2 = gen2.getVariations();
for (String[] s : v2) {
System.out.println(Arrays.toString(s));
}
System.out.println("Liczba permutacji: " + v2.size());
}
}