Skolem-Sequenzgenerator-Algorithmus

Question

Mein Lehrer möchte, dass ich eine Funktion schreibe, die einen ganzzahligen Wert N erhält und Array zurückgibt, dass seine Länge 2n ist und eine Skolem-Sequenz für den Wert enthält.

Zum Beispiel: Funktion (4) kehrt {4,2,3,2,4,3,1,1}

Ich habe Idee nicht, wie das zu tun.

Answer 1

Die Skolem Sequenz für eine Zahl n ist eine Folge von ganzen Zahlen der Größe 2 × n, die zwei Kriterien erfüllt:

1. für jede nicht-negative Zahl k < n , gibt es genau zwei Elemente s_ich und s_j in der Sequenz, so daß s_i = s_j = k

2. wenn s_i = s_j = k und i < j dann j − i = k

http://mathworld.wolfram.com/SkolemSequence.html

Grundsätzlich sehen, bedeutet dies, dass Sie benötigen, um Erstellen Sie eine Sequenz mit Zahlen von 1 bis n, wobei e ach Nummer erscheint zweimal. Um die Sequenz in eine Skolem-Sequenz zu verwandeln, müssen die beiden 1 nebeneinander liegen, die beiden 2 müssen eine Zahl zwischen sich haben, die 3 müssen 2 Nummern haben und so weiter.

Dieser Algorithmus ist schwieriger als man denken würde zu erstellen. Der einfachste Weg, dies zu tun, ist jede Permutation Ihrer Sequenz zu überprüfen und die erste, die funktioniert, zurückzugeben. Das ist (2n)! Komplexität, die schrecklich langsam ist. Hier ist eine Referenz für einen Algorithmus, der nicht n! Komplexität: http://www.cs.mun.ca/~dchurchill/pdf/honours.pdf

Ich habe den naiven Algorithmus in C++ geschrieben. Dies erzeugt Skolem-Sequenzen für jede gegebene Eingabe. Dieser Algorithmus ist schrecklich langsam, aber ich hoffe, Sie erhalten den Punkt:

#include<iostream> 
#include<vector> 
#include<algorithm> 
void start(int num, std::vector<int>& v) { //creates the |2n| sequence 
     for(int i = 1; i<=num; i++) { 
       v.push_back(i); 
       v.push_back(i); 
     } 
} 
bool check(std::vector<int>& v) { //checks to see if sequence is a skolem sequence 
     for(int i = 1; i<=v.size()/2; i++) { 
       auto j = std::find(v.begin(), v.end(), i); 
       auto k = std::find(j+1, v.end(), i); 
       if(k-j != i) { 
         return false; 
       } 
     } 
     return true; 
} 
void skolem(int num, std::vector<int>& v) { //permutes the vector to find skolem sequences 
     start(num, v); 
     while(std::next_permutation(v.begin(), v.end())){ 
       if(check(v)) 
         break; 
     } 
} 
int main() 
{ 
     int num; 
     std::cin>>num; 
     std::vector<int> v; 
     skolem(num, v); 
     std::cout<<"found it"<<std::endl; 
     print(v); 
} 

Dieser Algorithmus wird nur für kleine Zahlen arbeiten (weniger als 10). Wenn Sie größere Sequenzen verarbeiten müssen, schlage ich vor, dass Sie diesen Link oben sehen.