Frage Permutationsgenerator auf C


Ich brauche einen einfachen Algorithmus des Permutationsgenerators, der auf einfache C-Sprache angewendet werden könnte.


6
2017-10-05 08:58


Ursprung


Antworten:


Permutiert über Zahlen:

Um jede Permutation nutzen zu können, müssen Sie sich an die Druckfunktion anschließen.

#include <stdio.h>
#include <stdlib.h>

/**
   Read a number, N, from standard input and print the
   permutations.
 */

void print(const int *v, const int size)
{
  if (v != 0) {
    for (int i = 0; i < size; i++) {
      printf("%4d", v[i] );
    }
    printf("\n");
  }
} // print


void swap(int *v, const int i, const int j)
{
  int t;
  t = v[i];
  v[i] = v[j];
  v[j] = t;
}


void rotateLeft(int *v, const int start, const int n)
{
  int tmp = v[start];
  for (int i = start; i < n-1; i++) {
    v[i] = v[i+1];
  }
  v[n-1] = tmp;
} // rotateLeft


void permute(int *v, const int start, const int n)
{
  print(v, n);
  if (start < n) {
    int i, j;
    for (i = n-2; i >= start; i--) {
      for (j = i + 1; j < n; j++) {
    swap(v, i, j);
    permute(v, i+1, n);
      } // for j
      rotateLeft(v, i, n);
    } // for i
  }
} // permute


void init(int *v, int N)
{
  for (int i = 0; i < N; i++) {
    v[i] = i+1;
  }
} // init


int main()
{
    int *v = (int*) malloc(sizeof(int)*10);
    init(v, 10);
    permute(v, 0, 10);
    free(v);
}

5
2017-10-05 09:06



alle

Ich fand Algorithmen zur Erzeugung von Permutationen in lexikographischer Reihenfolge aus der Kunst der Computerprogrammierung (TAOCP):

http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Generation in lexikographischer Reihenfolge Es gibt viele Möglichkeiten, systematisch alle Permutationen einer gegebenen Sequenz zu erzeugen [Zitat benötigt]. Ein klassischer Algorithmus, der sowohl einfach als auch flexibel ist, basiert darauf, die nächste Permutation in der lexikographischen Ordnung zu finden, falls sie existiert. Es kann wiederholte Werte verarbeiten, für die es die verschiedenen Multiset-Permutationen jeweils einmal erzeugt. Selbst für gewöhnliche Permutationen ist es wesentlich effizienter, als Werte für den Lehmer-Code in lexikographischer Reihenfolge (möglicherweise unter Verwendung des faktoriellen Zahlensystems) zu erzeugen und diese in Permutationen umzuwandeln. Um sie zu verwenden, sortiert man die Sequenz in (schwach) ansteigender Reihenfolge (was ihre lexikografisch minimale Permutation ergibt) und wiederholt dann das Vorrücken zur nächsten Permutation, solange man sie findet. Die Methode geht auf Narayana Pandita im Indien des 14. Jahrhunderts zurück und wurde seitdem häufig wiederentdeckt.

Der folgende Algorithmus generiert lexikografisch die nächste Permutation nach einer gegebenen Permutation. Es ändert die gegebene Permutation an Ort und Stelle.

  1. Finde den größten Index k mit a [k] <a [k + 1]. Wenn kein solcher Index existiert, ist die Permutation die letzte Permutation.
  2. Finde den größten Index l mit a [k] <a [l]. Da k + 1 ein solcher Index ist, ist l gut definiert und erfüllt k <1.
  3. Tausche a [k] mit a [l].
  4. Umkehren Sie die Sequenz von [k + 1] bis einschließlich des letzten Elements a [n].

Nach Schritt 1 weiß man, dass alle Elemente genau nach der Position k eine schwach abnehmende Sequenz bilden, so dass keine Permutation dieser Elemente sie in lexikographischer Reihenfolge voranbringen wird; um voranzukommen, muss man ein [k] erhöhen. Schritt 2 findet den kleinsten Wert a [1], um a [k] zu ersetzen, und wenn sie in Schritt 3 ausgetauscht werden, bleibt die Sequenz nach Position k in schwach absteigender Reihenfolge. Die Umkehrung dieser Sequenz in Schritt 4 erzeugt dann ihre lexikographisch minimale Permutation und den lexikographischen Nachfolger des Anfangszustands für die gesamte Sequenz


4
2018-01-16 11:34



Dies ist ein klassischer Algorithmus, der unter anderem in Knuths TAOCP gefunden wurde.

Hier ist ein Beispiel, das ich für ein Projekt-Euler-Problem verwendet habe. Es erstellt alle Permutationen eines Strings in lexikographischer Reihenfolge und druckt sie auf stdout.

#include<stdio.h>
int main()
{
        char set[10]="0123456789";
        char scratch;
        int lastpermutation = 0;
        int i, j, k, l;
        printf("%s\n",set);
        while (!lastpermutation)
        {
                //find largest j such that set[j] < set[j+1]; if no such j then done
                j = -1;
                for (i = 0; i < 10; i++)
                {
                        if (set[i+1] > set[i])
                        {
                                j = i;
                        }
                }
                if (j == -1)
                {
                        lastpermutation = 1;
                }
                if (!lastpermutation)
                {
                        for (i = j+1; i < 10; i++)
                        {
                                if (set[i] > set[j])
                                {
                                        l = i;
                                }
                        }
                        scratch = set[j];
                        set[j] = set[l];
                        set[l] = scratch;
                        //reverse j+1 to end
                        k = (9-j)/2; // number of pairs to swap
                        for (i = 0; i < k; i++)
                        {
                                scratch = set[j+1+i];
                                set[j+1+i] = set[9-i];
                                set[9-i] = scratch;
                        }
                        printf("%s\n",set);
             }
        }
        return 0;
}

2
2017-10-13 21:35



Hier ist eine einfache rekursive Lösung, um alle Permutationen einer Menge von Zeichen zu erzeugen, die auf der Kommandozeile übergeben werden:

#include <stdio.h>
#include <string.h>

int perm(const char *src, int len, char *dest, char *destbits, int n) {
    if (n == len) {
        printf("%.*s\n", len, dest);
        return 1;
    } else {
        int count = 0;
        for (int i = 0; i < len; i++) {
            if (destbits[i] == 0) {
                destbits[i] = 1;
                dest[n] = src[i];
                count += perm(src, len, dest, destbits, n + 1);
                destbits[i] = 0;
            }
        }
        return count;
    }
}

int main(int argc, char *argv[]) {
    const char *src = (argc > 1) ? argv[1] : "123456789";
    int len = strlen(src);
    char dest[len], destbits[len];

    memset(destbits, 0, sizeof destbits);
    int total = perm(src, len, dest, destbits, 0);
    printf("%d combinations\n", total);

    return 0;
}

1
2018-02-27 09:47