Potrzebuje określić znak permutacji. Czy jest jakaś inna (szybsza) metoda niż przechodzenie po kolei po transpozycjach?
Dodam że potrzebuje określić ten znak przez zamieszanie związane z sortowaniem (funkcja wbudowana). Sortowanie jest stabilne. Czy może lepiej napisać swoje sortowanie które przy okazji będzie liczyć transpozycje. Jeśli tak, to jaki algorytm najlepiej zaimplementować, aby jak najprościej policzyć te transpozycje?
0
0
Policz ile razy po większej liczbie masz mniejszą jako wartość zliczaj pozycje takiego "przeskoku".
0
Nie do końca Cię rozumiem. Mogę prosić jaśniej?
0
123 - każda następna jest większa od poprzedniej = 0 - parzysta
132 - 3>2 na pozycji 1 = 1 - nieparzysta
213 - 2>1 na pozycji 2 = 2 - parzysta
231 - 3>1 na pozycji 1 = 1 - nieparzysta
312 - 3>1 na pozycji 2 = 2 - parzysta
321 - 3>2 na pozycji 2 oraz 2>1 na pozycji 1 = 3 - nieparzysta
1
Miałem podobne zadanie na ASD, tylko chyba z liczeniem sumy inwersji, a nie tylko znaku. Robiło się to przez zmodyfikowanego merge-sorta. Co do liczenia samego znaku permutacji - na StackOverflow jest zarys algorytmu liniowego. O ile dobrze zrozumiałem i jeżeli algorytm działa to wygląda on tak:
- Bierzesz pierwszą nieprzetworzoną jeszcze liczbę z ciągu - jest to początek cyklu.
- Dopóki liczba z aktualnego miejsca w ciągu jest różna od indeksu pierwszej liczby w ciągu - przejdź do pozycji w ciągu określanej przez tą liczbę.
- Mając długość cyklu obliczasz jego znak - cykl 1 elementowy jest parzysty, 2 elementowy nieparzysty, itd
- Dopóki są nieprzetworzone liczby w ciągu to wracasz do punktu 1.
- Sumujesz parzystości cykli by uzyskać parzystość całej permutacji.
0
Chyba się nie do końca rozumiemy: mam na myśli:
123 - parzysta bo nic
132 - nieparzysta bo (3,2) tylko zmienione
213 - nieparzysta bo (1,2) tylko
231 - parzysta bo (1,2) i (2,3)
312 - parzysta bo (1,3) i (2,3)
321 - nieparzysta bo (1,3)
0
123 - parzysta bo nic, ok
132 - nieparzysta bo (3,2) tylko zmienione, ok
213 - nieparzysta bo (1,2) tylko, owszem ale na drugiej pozycji od końca czyli dodajesz 2 nie 1, czyli parzysta
231 - parzysta bo (1,2) i (2,3), nie, liczy się tylko 3>1 bo 2<3, czyli nieparzysta
312 - parzysta bo (1,3) i (2,3), nie, liczy się tylko 3>1 ale na drugiej pozycji czyli dodajesz 2, czyli parzysta
321 - nieparzysta bo (1,3) liczy się tylko 3>2 na pozycji 2 plus 2>1 na pozycji 1, razem 3, czyli nieparzysta
porównujesz tylko sąsiednie liczby.
0
@ubuntuser:
Czy określanie znaku permutacji jest całym zadaniem? Jeśli nie, to podaj całe zadanie, bo szklanej kuli nikt nie ma, a znając całość problemu można wykminić coś lepszego.
Sprawdzałeś czy na pewno wykonujesz liniową ilość kroków?
@_13th_Dragon:
213 jest nieparzysta: http://www.wolframalpha.com/input/?i=sign+of+permutation%282%2C+1%2C+3%29
0
Poprawiłem tamten kod żeby działał szybciej i w temat można uznać za zamknięty, algorytm który przytoczył Wibowit jest w porządku, chyba, że @_13th_Dragon chce jeszcze coś dopisać.
0
Algorytm który podałem daje dokładnie takie same wyniki co algorytm ot @Wibowit jednak jest znacznie prostszy i szybszy.
bool cnt(const string &str)
{
bool sum=0;
for(size_t i=0;i<str.length();++i) for(size_t k=i+1;k<str.length();++k) if(str[i]>str[k]) sum=!sum;
return sum;
}
0
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Main {
public static boolean checkParityWibowit(List<Integer> permutation) {
boolean[] used = new boolean[permutation.size()];
boolean parity = false;
for (int i = 0; i < permutation.size(); i++) {
if (!used[i]) {
int index = i;
do {
used[index] = true;
parity ^= true;
index = permutation.get(index);
} while (index != i);
parity ^= true;
}
}
return parity;
}
public static boolean checkParity13Dragon(List<Integer> permutation) {
boolean parity = false;
for (int i = 0; i < permutation.size(); ++i) {
for (int k = i + 1; k < permutation.size(); ++k) {
if (permutation.get(i) > permutation.get(k)) {
parity ^= true;
}
}
}
return parity;
}
public static void main(String[] args) throws Exception {
final int Size = 12345;
List<Integer> permutation = new ArrayList<>(Stream.iterate(0,
seed -> seed + 1).limit(Size).collect(Collectors.toList()));
Collections.shuffle(permutation, new Random(0));
permutation = Collections.unmodifiableList(permutation);
long time;
time = System.currentTimeMillis();
System.out.println(checkParityWibowit(permutation));
System.out.println("Wibowit time: "
+ (System.currentTimeMillis() - time));
time = System.currentTimeMillis();
System.out.println(checkParity13Dragon(permutation));
System.out.println("13thDragon time: "
+ (System.currentTimeMillis() - time));
}
}
run:
true
Wibowit time: 1
true
13thDragon time: 226
BUILD SUCCESSFUL (total time: 0 seconds)
0
Hmm chyba udało mi się uzyskać liniowy czas.
Na końcu trochę funkcja wariuje, może dlatego że generowanie danych trochę trwało (korzystałem z tego generowania co miałem, nie pisałem na potrzebę testu). Oczywiście generowanie danych nie jest wliczone. Ale czemu tak wariuje, nie wiem, więc strzelam.
Dla zbioru o liczności 100 000 - 90 ms, dla 1 000 000 - 230
Pisane oczywiście w Scali.
Zaraz dorzucę kod ale jeszcze poprawić trochę muszę inne rzeczy.
0
@_13th_Dragon:
Jak już masz takie ciśnienie na liczenie inwersji to proszę bardzo:
import java.util.Arrays;
import java.util.Random;
public class Main {
public static long countInversionsWibowit(int[] buffer, int[] input,
int start, int next) {
if (next - start <= 1) {
return 0;
}
long inversions = 0;
int middle = start + (next - start) / 2;
inversions += countInversionsWibowit(buffer, input, start, middle);
inversions += countInversionsWibowit(buffer, input, middle, next);
System.arraycopy(input, start, buffer, start, next - start);
int left = start;
int right = middle;
int store = start;
while (left < middle && right < next) {
if (buffer[left] <= buffer[right]) {
input[store++] = buffer[left++];
} else {
inversions += middle - left;
input[store++] = buffer[right++];
}
}
while (left < middle) {
input[store++] = buffer[left++];
}
while (right < next) {
input[store++] = buffer[right++];
}
return inversions;
}
public static long countInversionsWibowit(int[] input) {
int[] buffer = new int[input.length];
return countInversionsWibowit(buffer, input, 0, input.length);
}
public static long countInversions13Dragon(int[] input) {
long inversions = 0;
for (int i = 0; i < input.length; ++i) {
for (int k = i + 1; k < input.length; ++k) {
if (input[i] > input[k]) {
inversions++;
}
}
}
return inversions;
}
public static void main(String[] args) throws Exception {
final int Size = 123456;
int[] input = new Random(0).ints(Size).toArray();
long time;
time = System.currentTimeMillis();
System.out.println(countInversionsWibowit(
Arrays.copyOf(input, input.length)));
System.out.println("Wibowit time: "
+ (System.currentTimeMillis() - time));
time = System.currentTimeMillis();
System.out.println(countInversions13Dragon(
Arrays.copyOf(input, input.length)));
System.out.println("13thDragon time: "
+ (System.currentTimeMillis() - time));
}
}
Sortowanie przez złączanie połączone z liczeniem inwersji.
Wyniki:
run:
3799830837
Wibowit time: 21
3799830837
13thDragon time: 7052
BUILD SUCCESSFUL (total time: 7 seconds)