Funkcja next_permutation()

0

Mam sobie n+1 liczb.
Kiedy podam n=4 to ma mi wypisać 1 3 0 2 4
Kiedy podam n=3 to ma mi wypisać np. 2 0 3 1
Liczby nie mogą się powtarzać.

Kombinowałem coś z funkcją

next_permutation()

ale kompeltna klapa.
Może ktoś ma pomysł jak wykorzystać tą funkcję żeby mi te liczby tak ładnie wypisało?

0

Ale o co ci chodzi? Żeby wypisać permutację ciągu liczb [0, ..., n], żeby dwa kolejne elementy ciągu nie różniły się o 1?

  • dla 0 < n < 3 się nie da.
  • inaczej wypisujesz rosnąco liczby nieparzyste ciągu, a potem rosnąco liczby parzyste - i to na tyle.
0

Dzięki za odp. Nie da się tego zrobić przy pomocy tej funkcji?

0

Dzięki za odp. Nie da się tego zrobić przy pomocy tej funkcji?

0

Da się (wywoływać procedurę next_permutation aż do momentu uzyskania prawidłowego wzorca - bo, jak mi się zdaje, istnieje pewna ilość prawidłowych permutacji). Jednak oczekiwanie na poprawną permutację już dla niewielkich wartości n staje się zbyt długie.

Edit: mam jednak pewien pomysł: mamy ciąg liczb [0..n] (np. [0, 1, 2, 3].

  1. Bierzemy dwa pierwsze elementy, z których pierwszy jest na pozycji i - tutaj elementy to [0, 1] oraz i=0 (przyjmijmy, że pozycje liczymy od 0).
  2. Jeżeli te dwa elementy nie mogą istnieć obok siebie (jeden różni się o 1 od drugiego, jak tutaj [0, 1]), to robimy następną permutację wszystkich elementów od początku aż do elementu za naszą sprawdzaną parą - u nas by to było next_permutation(tab, tab+n+3). Jedynym wyjątkiem jest to, gdy nie zgadzają się dwa ostatnie elementy - wtedy permutujemy cały ciąg. Potem wracamy do punktu 1. Inaczej bierzemy dwa następne elementy.
  3. Kończymy, jeśli cały ciąg jest OK.

Przykład dla n=6:

0123456        <=== ciąg
!!             <=== elementy o pozycjach 0 i 1 nie zgadzają się
:::            <=== w takim razie permutujemy pozycje od 0 do 2

0213456        <=== ciąg; potem liczymy od nowa
++             <=== OK
 !!            <=== elementy o pozycjach 1 i 2 nie zgadzają się
::::           <=== permutujemy pozycje od początku (0) do 2+1=3

0231456
++
 !!            <=== elementy o pozycjach 1 i 2 nie zgadzają się
::::           <=== permutujemy od początku do 3

0312456
++
 ++
  !!           <=== złe elementy 2 oraz 3
:::::          <=== czyli permutujemy od początku aż do 3+1=4

0314256        <=== kolejny ciąg; teraz pokazuję tylko pierwszy błąd
     !!        <=== elementy o pozycjach 5 i 6 nie zgadzają się
:::::::        <=== to dwa ostatnie elementy, więc permutujemy cały ciąg

0314265
     !!
:::::::

0314526
   !!
::::::

0315246        <=== CIĄG JEST OK
0
#include<iostream>
using namespace std;

int main(){
    long unsigned int n, *arr, j=0, k=1;
    cin>>n;
    arr = new long unsigned int[n+1];
    for(long unsigned int i=0; i<(n+1); i++,j++){
             if(n<=2){ cout<<"NIE"; break;}
             if(j>n) j=(k++);
             cout<<(j++)<<" ";
             j++;
    }
    return 0;
} 

Napisałem coś takiego, ale przy moich testach uzyskuje błędną odp. Gdzie jest pies pogrzebany?

0

Hmm... zauważ, że dla n=0 powinno wypisać 0.

0

mnbvcX jesteś GENIUSZEM! wprowadziłem warunek z zerem i zagrało:D Dziękuję Ci serdecznie!
Trochę mnie tylko czas niepokoi 0.22s :/ Jest na to może jakiś szybszy algorytm?

0

Pokaż cały kod którym to teraz generujesz?...

0
#include<iostream>
using namespace std;

int main(){
    long unsigned int n, *arr, j=0, k=1;
    cin>>n;
    arr = new long unsigned int[n+1];
    for(long unsigned int i=0; i<(n+1); i++,j++){
             if(n==0) cout<<"0";
             if(n<=2){ cout<<"NIE"; break;}
             if(n==3){cout<<"2 0 3 1"; break;}
             if(j>n) j=(k++);
             cout<<(j++)<<" ";
             j++;
    }
    return 0;
}
 
0

Nie lepiej tak?

#include<iostream>
using namespace std;
 
int main(){
    long unsigned int n, *arr, j=0, k=1;
    cin>>n;
    arr = new long unsigned int[n+1];
    if(n == 0) cout << "0";
       else if(n <= 2) cout << "NIE";
       else if(n == 3) cout << "2 0 3 1";
       else
            for(long unsigned int i=0; i<(n+1); i++,j++){
               if(j>n) j=(k++);
               cout<<(j++)<<" ";
               j++;
            }
    return 0;
}

P.S. W ogóle po co Tobie ta deklaracja arr?

0

Właściwie nie jest mi potrzebna. Teraz czas wykonania to 0.19s :/ Wydaje mi się, że mój algorytm jest średni.

0

Najszybsze powinno być użycie funkcji fwrite do wypisania całego wyjścia (które może być dość długie) za jednym razem.
Tak poza tym, np. na SPOJ-u (stamtąd chyba jest to zadanie) jest odpowiednio nowa wersja glibc, która pozwala na używanie funkcji z serii unlocked, np. fread_unlocked, fwrite_unlocked.

0

Nie znam tych funkcji i nie wiem jak działają w praktyce, może jakiś kod? Zadanie faktycznie jest ze spoju, mam je zaakceptowane, ale tak dla własnej ciekawości chciałbym poznać algorytm który wykonałby to szybciej...

1 użytkowników online, w tym zalogowanych: 0, gości: 1