Sortieren von zahlen -Problem bei der Ausgabe-Bedingung

Royale

Moin,
ich bearbeite grade folgendes Problem. 8 Zahlen sind miteinader verbunden, die verbundenen zahlen sollen sich um mehr als 1 unterscheiden, ich muss alle Zahlen von 1 bis 8 unterbringen. Das Schema sieht so aus (Die Zahlen stehen für die Nummereirung):

http://www.bilder-hochladen.net/files/hxm-b-jpg-nb.html

Nun stellt sich mir die Frage, ob es etwas effiktiveres gibt, als eine IF-Abfrage, nachdem man die Permutationen berechnet hat, denn eine IF-Abfrage wäre ewig lang und garantiert nicht ganz fehlerfrei^^
Hier mein bisheriger Algorithmus:

#include <stdio.h>

void perm(int anz, int array[], int start);
void ausgabe(int anz, int array[]);

int main() {
	int loesung[8];
	int i;

	for (i = 0; i < 8; i++) {
		loesung[i] = i;
	}
	perm(8, loesung, 0);

}

void perm(int anz, int array[], int start) {
	int i, sav;
	if (start < anz) {
		sav = array[start];
		for (i = start; i < anz; i++) {
			array[start] = array[i];
			array[i] = sav;
			perm(anz, array, start + 1);
			array[i] = array[start];
		}
		array[start] = sav;
	}
	else {
		ausgabe(anz, array);
	}
}

void ausgabe(int anz, int array[]) {
	int i;
	for (i = 0; i < anz; i++) {              

/*Hier weiß ich keine sinnvolle Bedingung außer einer stark verklauselten IF-Bedingung */
		printf("%d ", array[i]);
	}
	printf("\n");
}

Belli

Anstatt erst eine vollständige Permutation zu berechnen, und dann in der Ausgabefunktion zu prüfen, ob sie die Bedingungen erfüllt, würde ich in der rekursiven Funktion nach jedem Einsetzen einer Zahl entweder:

eine Funktion aufrufen, die die Bedingungen für die bereits verteilten Zahlen prüft - dann kannst Du nämlich viele Permutationen schon sehr früh abbrechen --> Performancegewinn,

oder:

eine Funktion aufrufen, die die Bedingungen für genau die gerade eingesetzte Zahl prüft, Performancegewinn wie oben, allerdings müsste man verschiedene Prüffunktionen schreiben, und sich überlegen, wie man am einfachsten die jeweils richtige ansteuert.

Sobald eine Bedingung nicht erfüllt ist, einen Rekursionsschritt zurück und weitermachen.

Royale

hmm und iw emache ich das? ichw ar schon froh, dass ich die permutation honbekommen habe^^

Ich denke nicht, dass Performance bei 40320 Permutationen wirklich von großer Bedeutung ist.

Wie dem auch sei, mit einer kleinen Hilfsfunktion lässt sich eine solche if-Abfrage einigermaßen übersichtlich gestalten:

int valid_edge(int *array, size_t i, size_t j) {
  int x = array[i] - array[j];
  return x > 1 || x < -1;
}

/* ... */

if(valid_edge(array, 0, 1) &&
   valid_edge(array, 0, 2) &&
   valid_edge(array, 0, 3) &&
   valid_edge(array, 1, 4) &&
  /* ... */

Ist das nicht genug, fällt mir etwa Folgendes ein:

#define ARRAY_SIZE(x) (sizeof(x) / sizeof(*x))

int int_abs(int x) { return x < 0 ? -x : x; }

int valid_graph(int array[8]) {
  static size_t const net[][2] = {
    { 0, 1 }, { 0, 2 }, { 0, 3 },
    { 1, 4 }, { 1, 5 },
    { 2, 4 }, { 2, 5 }, { 2, 6 },
    { 3, 5 }, { 3, 6 },
    { 4, 7 },
    { 5, 7 },
    { 6, 7 }
  };

  size_t i;

  for(i = 0; i < ARRAY_SIZE(net); ++i) {
    if(int_abs(array[net[i][0]] - array[net[i][1]]) < 2) {
      return 0;
    }
  }

  return 1;
}

wobei jedes Zahlenpar eine Kante des Graphen darstellt.

Royale

hmmm, ich verstehe deinen code noch nicht so ganz, ich bin erst seit 4 wochen dabei c zu lernen. Du defnierst dir ein array mit den Beziehungen, wer mit wem verbunden ist.
Doch denn schritt dann verstehe ich nicht ganz. Ich habe es mit einer IF Abfrage probiert, doch da aht sich ein Fehler einegschlichen, und wie ich erwartet habe, finde ich ihn nicht^^.
So siehts bei mir mit der Abfrage bisher aus:

void ausgabe(int anz, int array[]) {
	int i,hilf1,hilf2,hilf3,hilf4;
	for (i = 0; i < anz; i++) {
		hilf1 = array [0] - array[1];                            /*für 1*/
		hilf2 = array [0] - array[2];
		hilf3 = array [0] - array[3];

		if ((hilf1 >1 || hilf1 < -1) && ( hilf2 >1 || hilf2 < -1) && (hilf3 >1 || hilf3 < -1))   /* für 2*/
		   { hilf1 = array[1] - array [2];
		     hilf2 = array [1] - array[4];
		     hilf3 =array [1] -array [5];

             if ((hilf1 >1 || hilf1 < -1) && ( hilf2 >1 || hilf2 < -1) && (hilf3 >1 || hilf3 < -1) && (hilf4 >1 || hilf4 < -1))   /*für 3*/
              { hilf1 = array[2] -array [3];
                hilf2= array [2] - array [5];
                hilf3= array [2] - array [6];
                hilf4= array [2] -array[4];

                if ((hilf1 >1 || hilf1 < -1) && ( hilf2 >1 || hilf2 < -1) && (hilf3 >1 || hilf3 < -1))                      /*für 4*/
                {hilf1=array [3] -array[5];
                hilf2= array[3] -array[6];

                        if ((hilf1 >1 || hilf1 < -1) && ( hilf2 >1 || hilf2 < -1))                                      /*für 5*/
                           { hilf1 = array [4] - array[5];
                             hilf2 = array[4] -array [5];

                             if  ((hilf1 >1 || hilf1 < -1) && ( hilf2 >1 || hilf2 < -1))                         /*für 6 */
                                 { hilf1=array[5]-array[7];
                                   hilf2=array[5]-array[6];

                                   if ((hilf1 >1 || hilf1 < -1) && ( hilf2 >1 || hilf2 < -1))  /*für 7*/
                                      {hilf1 = array[6] -array[7];

                                             if (hilf1 >1 || hilf1 < -1)
                                                {printf("%d ", array[i]);
	}}}}}}}}
	printf("\n");

Belli

seldon schrieb:

Ich denke nicht, dass Performance bei 40320 Permutationen wirklich von großer Bedeutung ist.

Ähhhhh .... ja! Ich hab mir gar keine Gedanken darüber gemacht, daß es so (relativ) wenige sind.

Royale schrieb:

hmm und iw emache ich das? ichw ar schon froh, dass ich die permutation honbekommen habe^^

http://img593.imageshack.us/img593/5307/zwischenablage01u.jpg :p