Mam kod:
int[] tab = new int[10];
sort(tab);
do
{
for(int i = 0; i < tab.length; i++)
{
int[] subTab = tab.sub(0, i);
if (DoIt(subTab))
{
// TUTAJ
}
}
}
while(next_permutation(tab));
W miejsce TUTAJ chciałbym umieścić kod odpowiedzialny za przeskoczenie permutacji dla danego indexu i. Tzn. że jeżeli mamy permutację: [1,3,2,4] i subTab [1,3] spełnia warunki to chce od razu przeskoczyć do [1,4,2,3] itd. Jak to zrobić najszybciej?
Jeśli przez następną pemutacje dla 42137 sub = 421 rozumiesz 42317 To możesz zrobić to tak, tworzysz pomocniczą tablice z posortowanym oryginalnym ciągiem, i drugą pomocniczą tablice(1,2,3,4,7) z a numerami indeksów(0,1,2,3,4) do pierwszej, jeśli możesz do funkcji tworzącej permutacje dać tablice indeksów, to super:) jeśli nie będziesz musiał parsować permutacje na tablice ułożenia indeksów(można to zrobić w czasie liniowym wiec lajt ;)). powiedzmy teraz że masz permutacje (4 2 1 3 7) sub (4 2 1) czemu odpowiadają indeksy P[] = (3 1 0 2 4) i S[] = ( 3 1 0) i S2[] (2 , 4) (S2 fizynie nie istnieje, to ta część tablicy P co nie należy do S) Jeśli S[S.lenght-1]+1 %P.lenght(czyt. zwieksz modulo o 1) jest rożne od 0 to:
1:Szukasz w S2 wartosci co jest oddalona o najmniejszą ilość operacji S[S.lenght-1]+1 %P.lenght od S[S.lenght-1] można to zrobić w czasie liniowym, zamieniasz miejscami p[s.leanght-2] z tym co znalazłeś sortujesz przez zliczenie S2.
Jest równe 0
wykonujesz 1 Tyle że w miejsce S[S.lenght] wstawiasz S[S.lenght-2] jeśli jest to poza zakresem po prostu sortujesz prze zliczenie :).
Wczytujesz w miejsce indeksów wartosć P[i] = Posrtowanatab[P[i]];
@topik92 dzięki za zainteresowanie tematem, jednak nie bardzo mogę się rozczytać zapisu, mógłbym Cię prosić o zapisanie algorytmu w postaci pseudokodu, lub ponowne wypunktowanie co i jak? Dziękuje za pomoc.
Żebym sie na darmo nie produkował napisz co uważasz za natepna permutacje dla ciągów p =(1 2 3 4 5) s=(1 2 3), p =(4 2 3 1) s=(4) , p =(4 2 1 3 7) s = (4 2 1)
Gdybyś mógł dość w łatwym języku rozpisać algorytm to bym bradzo dziękował:)
int[] tab = new int[10];
sort(tab);
do
{
for(int i = 0; i < tab.length; i++)
{
int[] subTab = tab.sub(0, i);
if (DoIt(subTab))
{
int[] subTab2 = tab.sub(i+1);
subTab2.SortDesc();
subTab2.copyTo(tab, i+1,subTab2.len);
// zagwarantuje skok do "nastepnej" permutacji w kolejnym obiegu while
}
}
}
while(next_permutation(tab));
//To musisz miec przygotowane przed
int[] tab1 = { wczytaj liczby};
tab.sort();
int[] tablicaPom = {przepisz liczby z tab1} // PRZEPISZ a nie przekazuj referancje
Dictionary<int,int> parse; // diciornary to dotnetowa nazwa #tablicy
for(i =0, i<tablicaPom.lenght ;i ++) // żeby wykonać parsowanie w czasie liniowy
{
parse.add(tablicaPom[i],i);
}
//funkcja
int[] Parsuj(Dictionary<int,int> parse, int[] toParse) //Przepisuje Ci permutacje liczb na permutajce "wskaźników"
// jest to ważne ponieważ ilość pól w tablicy jest zgóry określona, skonczona i uporządkowana i nie obchodzi Cie jaki typ danych
//przechowuje tablica
int[] outPut;
for(i=0;i<toParse.lenght,i++)
outPut[i] = parse.GetKey(toParse[i]);
return output
//funkajca
OminPermutacje(int[] tab,int[] subTab,Dictionary<int,int> parse) // nie kontroluje danych Ty powinieneś ;)
int[] P =Parsuj(parse,tab,);
int[] S =Parsuj(parse,subTab);
if(s.lenght == 0) //np. P= 0123 s= null
//twójPomysl
if(P[S.lenght-1]== S.lenght-1) // najwieksza mozliwa liczba dla 01234 to 4
if(S.lenght==1) // np 3210 i 3
// tu chciałeś false...
else
temp =ZnadzNajbliże(S,S[S.lenght - 1],P.lenght) // indeks najblizszej wartosci
Zamien(P, temp,S.lenght-2) // tablica[] indeks1 indeks2
Sortuj(P,S.lengh-2) //Sortuj przez w stawienie badź zliczenie tablice P odpodanego indeksu do konca)
else
temp =ZnadzNajbliże(S,S[S.lenght - 1],P.lenght) // tablica do przeszukania, wartosc, zakres
Zamien(P, temp,S.lenght-1) // tablica[] indeks1 indeks2
Sortuj(P,S.lengh-1) //Sortuj przez w stawienie badź zliczenie tablice P odpodanego indeksu do konca)
// to co teraz masz w P to indeksy do wartosci z tablicaPomocnicza nowej permutacji
int[] nPermutacja
for(i=0;i<p.lenght, i++)
nPermutacja[i] = tablicaPomocnicza[P[i]];
// funkcja
ZnadzNajbliże(int[] S, int value, int n) //dla P = 0 3 5 1 2 4 n jest równe 6
int[] temp;
for(i=0, i<s.lenght, i++)
temp[i] = (S[i] + n - value)%n;
return temp.Min();
Potrafił bym to ąłtwo wytłumczyć na papierze ale z poziomu forum nie da rady :/