Funkcja next_permutation()

Odpowiedz Nowy wątek
2011-07-18 18:23
YO
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?

Pozostało 580 znaków

2011-07-18 18:44
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.

Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535
edytowany 1x, ostatnio: mnbvcX, 2011-07-18 18:45

Pozostało 580 znaków

2011-07-18 19:14
YO
0

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

Pozostało 580 znaków

2011-07-18 19:15
YO
0

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

Pozostało 580 znaków

2011-07-18 20:03
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

Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535
edytowany 2x, ostatnio: mnbvcX, 2011-07-18 20:21

Pozostało 580 znaków

2011-07-18 20:36
YO
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?

Pozostało 580 znaków

2011-07-18 22:03
0

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


Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535

Pozostało 580 znaków

2011-07-18 23:00
YO
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?

Pozostało 580 znaków

2011-07-19 09:35
0

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

Pozostało 580 znaków

2011-07-19 10:41
YO
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;
}
 

Pozostało 580 znaków

2011-07-19 10:44
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?


Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535
edytowany 2x, ostatnio: mnbvcX, 2011-07-19 10:45

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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