3. Alle Permutationen ausgeben

Alle Permutationen ausgeben

  • C

    Habe ein kleines Programm geschreiben, welches alle Permutationen eines int array ausgeben sollte. Das klappt auch bis 3 Array-Elemente, ab dann werden nur noch die Hälfte der Permutationen ausgegeben, dafür doppelt. Erkennt jemand den(die) Fehler?

    #include <iostream>
using namespace std;

const int ANZ=4;

int faculty(int n)
{
	if(n==0)
	{
		return 1;
	}
	else
	{
		int value=1;
		for(n;n>0;n--)
		{
			value*=n;
		}
	return value;
	}
}

int* algo(int* a)
{
	int l;
	for(int i=0; i<faculty(ANZ);i++)
	{
		l=a[(i%ANZ)];
		a[(i%ANZ)]=a[(i+1)%ANZ];
		a[(i+1)%ANZ]=l;

		cout << "Permutation " << i+1 << ": ";
		for(int j=0;j<ANZ;j++)
		{
			cout <<a[j];
		}
		cout << endl;
	}	
	return 0;
}

int main()
{
	int a[ANZ];
	for (int i=0; i<ANZ;i++)
	{
		a[i]=i;
	}
	algo(a);

	return 0;
}

    Danke Gruss cof

    0
  • J

    ich habe zwar keine lösung für dein problem, aber vielleicht interessiert dich next_permutation aus der stl.

    0
  • ?

    ich weiss jetzt zwar nicht was permutations sind 🙄, aber bei mir kommt nichts doppelt raus sondern das:
    Permutation 1: 1023
    Permutation 2: 1203
    Permutation 3: 1230
    Permutation 4: 0231
    Permutation 5: 2031
    Permutation 6: 2301
    Permutation 7: 2310
    Permutation 8: 0312
    Permutation 9: 3012
    Permutation 10: 3102
    Permutation 11: 3120
    Permutation 12: 0123
    Permutation 13: 1023
    Permutation 14: 1203
    Permutation 15: 1230
    Permutation 16: 0231
    Permutation 17: 2031
    Permutation 18: 2301
    Permutation 19: 2310
    Permutation 20: 0312
    Permutation 21: 3012
    Permutation 22: 3102
    Permutation 23: 3120
    Permutation 24: 0123

    wenn das beabsichtigt war, dann sag mal welchen compiler du benutzt oder versuch mal meine version, die ich umgeschrieben habe ( aufgemotzt 😉 ):

    #include <iostream> 
#include <fstream>

inline int fac ( const int n )  { 
  return n < 2 ? 1 : n * fac ( n - 1 );
};

template<class T>
void permutation ( T* array, const std::size_t size, std::ostream& out = std::cout )  {
  for ( int i = 0; i < fac ( size ); )  { 
    T t = array[( i % size )]; 
    array[( i % size )] = array[( i + 1 ) % size]; 
    array[( i + 1 ) % size] = t; 

    out << "Permutation " << ++i << ":\t"; 
    for ( int j = 0; j < size; ) 
      out << array[j++]; 
    out << std::endl; 
  }    
}; 

int main() 
{ 
char* a[4] = { "0", "1", "2", "3" };  
std::fstream outputFile ( "permutation.txt", std::ios::out );

  permutation ( a, 4 );
  permutation ( a, 4, outputFile ); 

std::cin.clear ();
std::cin.ignore ( std::cin.rdbuf () -> in_avail () );
std::cin.get ();
return 0; 
}

    was auch immer

    0
  • C

    danke erst mal für deine Mühen.

    Allerdings hat deine Ausgabe auch doppelte Ausgaben. z.B Permutation 24 und 12 erzeugen beide 0123.
    Eine Permutation ist eine andere Anordung der Elemente.
    bei 3 Elementen wäre es:
    123
    132
    321
    312
    231
    213

    bei 4 elementen sind es 4! Anordungen also 24.

    Habe deinen Code noch nicht angeschaut, kommt aber noch

    0
  • H

    std::next_permutation hat dich wirklich nicht weitergebracht 😞
    Was störte dich denn dabei?

    0
  • ?

    ich glaub vielleicht versteh ich jetzt. aender mal folgende zeile :

    for ( int i = 0; i < fac ( size ) / 2; )  //da ab der haelfte alle permutations wiederhohlt werden

    was auch immer

    0
  • C

    @helium: ehrlich gesagt, habe ich das noch nicht angesehen, möchte denn algorithmus man selbst finden.
    @was auch immer: es gibt aber fac(size) pernutationen. er gibt einfach nur die haelfte aus, diese dafür doppelt. dh es fehlen 50% der Permutationen.

    gruss cof

    0
  • I

    Wahrum nicht rekursive Funktione benutzen? Oder std::stack? Oder sogar deine eigene Stack Implementierung?

    0
  • C

    habe mir überlegt ob ichs rekursiv machen soll, bin aber nicht auf eine vernünftige Überlegung gestossen.

    Wenn ich einen Stack brauchen würde, müsste ich die Permutationen schon alle kennen um diese auf den stack zu pushen, allerdings rechnet der Algorithmus nicht alle aus, dh der Algo ist falsch.

    0
  • I
     

    include <iostream>
#include <algorithm>

void permut (int arr[], int n, int * prev, int start = 0)
{
  if (n <= start) {
    for (int i = 0; i < n; i++) {
      cout<<prev[i]<<" ";
    }
    cout<<endl;
    return;
  }
  for (int i = start;  i < n; i++) {
     prev[start] = arr[i];
     swap (arr[i], arr[start]);
     permut (arr, n, prev, start + 1);
     swap (arr[i], arr[start]);
  }
}

int main (void) {
    const int sz = 3;
    int arr[sz], prev[sz];
    for (int i = 0; i < sz; i++)
      arr[i] = i;

    permut (&arr[0], sz, &prev[0]);
    return 0;
}
    0
  • ?

    kann man auch ohne pointer diese Beispiel lösen?

    0
Anmelden zum Antworten