[algoritmo] tutte le combinazioni

[djpeppe]

ciao a tutti,
devo fare un programma che scrive tutte le combinazioni che si possono fare con i numeri 1 2 3 4 5.
es.
12345
12354
12435
51432 ecc.

grazie ciao

[akyra]

mi sembra molto esercizio di programmazione per l'università....
dato un insieme n di elementi, il numero di permutazioni possibili è n! (n fattoriale).

qui trovi l'algoritmo in pseudocodice (sezione "124.4.4 Permutazioni")
http://www.to.infn.it/groups/group4/...pseudo-permuta

qui trovi un esempio in C

http://www.to.infn.it/groups/group4/...-9.27.131.html

al paragrafo "131.3.4 Permutazioni"....comunque se vuoi un consiglio io almeno proverei a farlo

[andbin]

Originariamente inviato da akyra

dato un insieme n di elementi, il numero di permutazioni possibili è n! (n fattoriale).

"combinazioni" e "permutazioni" sono 2 cose differenti ....

[akyra]

nella richiesta mi sembrava evidente che intendesse "permutazioni", dato che non aveva specificato l'eventuale lunghezza m delle possibili combinazioni ricavate dagli n numeri di cui è composto l'insieme di partenza...probabilmente avrei dovuto aggiungere:"forse intendevi 'permutazioni' e non 'combinazioni'?"

[djpeppe]

allora il programma mi deve stampare tutte le combinazioni possibili combinando i numeri '1' '2' '3' '4' '5' senza ripeterli( 11125 non è accettabile) e formando un numero di 5 cifre. cioè l'output del programma dovrebbe essere così:
12345
12354
12435
12453
....
45312
.....
ecc.
"sono stato spiegato"??????
help me che all'università mi stanno massacrando

[djpeppe]

ok ho trovato su un altro sito questo codice e funziona perfettamente.

#include <iostream>
#include <fstream>
#include <cstdlib>

class Combinations
{
	private:
		int *Elements;
		int *Indexes;
		int Length;
		bool End;
	int i;
	public:

		Combinations (int *Elements,int NumElem)
			{
		    
		this->Length = NumElem;
        this->Elements = new int[Length];

		memset(this->Elements,0,Length * sizeof(int));

        if (Length > 0)
            this->Indexes = new int[Length-1];
			memset(this->Indexes,0,sizeof(int) * Length - 1);

        for (int i = 0; i < Length; i++)
            this->Elements[i] = Elements[i];

        End = Length < 1;
    }

    bool hasNext()
    {
        return !End;
    }

    int* next ()
    {
        if (End)
            return NULL;

        int *result = new int[this->Length];

        memset(result,0,this->Length * sizeof(int));
		for (int i = 0; i < Length; i++)
            result[i] = Elements[i];

        for (i = 0; i < Length-1; i++)
        {
            int obj = result[i+Indexes[i]];

            for (int j = i+Indexes[i]; j > i; j--)
                result[j] = result[j-1];

            result[i] = obj;
        }

        int carry = 1;

        for (i = Length-2; i >= 0; i--)
        {
            Indexes[i] += carry;

            if (Indexes[i] > Length-i-1)
            {
                Indexes[i] = 0;
                carry = 1;
            }
            else
                carry = 0;
        }

        if (carry == 1)
            End = true;

        return result;
    }
};

using namespace std;

int main(void)
{
	int elems;
	cout <<"Number Generator by Peppe Mercury & Ciccio Cat, 2007" <<endl <<endl;
	cout <<"Quanti elementi vuoi inserire?" << endl;
	cin >> elems;

	int *pNumbers = new (nothrow) int[elems];
	cout <<"Inserire gli elementi." << endl;

	for (int i = 0; i < elems; i++)
		cin >> pNumbers[i];
		
	cout << endl;	

	Combinations *c = new Combinations(pNumbers,elems);
			
	ofstream f;
	f.open("Combo.txt",ios::out);

	while (c->hasNext())
		{
			int *arr = c->next ();

			for (int i = 0; i < elems; i++)
				{
					cout << arr[i] << " ";
					f << arr[i] << " ";
				}
				cout <<endl;
				f <<endl;
				
			
			delete arr;
		}
	
	f.close();
	cout <<"Combinazioni salvate nel file Combo.txt " << endl;

	system("PAUSE");

	delete[] pNumbers;
	delete c;

	
	
	return 0;
}

ora.... mi servirebbe farlo con javascript:
vorrei che le combinazioni siano inserite in un link es. http:www.hwupgrade.it/*****.html

si può fare ma io sono un capra in javascript, mi aiutate?

[Oceans11]

vedete che in realtà quelle sono disposizioni....ecco perchè hanno tratto in inganno...se è importante la posizione (l'ordine insomma) degli elemeti allora sono disposizioni...ne sono (quasi) certo

[andbin]

Originariamente inviato da djpeppe

ok ho trovato su un altro sito questo codice e funziona perfettamente.

Mi sembra di aver già visto questo codice ...
È la riscrittura in C++ (fatta da un'altra persona) di una mia classe Java ... che però, nota bene, genera permutazioni e non combinazioni.

Originariamente inviato da Oceans11

vedete che in realtà quelle sono disposizioni....

Come ho già detto, quelle sono "permutazioni". Le permutazioni possono essere viste come un caso "particolare" di disposizioni semplici (senza ripetizione) in cui si pone k=n.

[djpeppe]

si lo so andbin, sei un grande!
io non capisco niente di combinazioni, permutazioni, disposizioni ecc.
ora vorrei sapere se riuscite a portarla a javascript, grazie

[suppaman]

Originariamente inviato da djpeppe

io non capisco niente di combinazioni, permutazioni, disposizioni ecc.

La teoria è abbastanza semplice credo la trovi all'inizio di un testo di probabilità o anche nei testi delle superiori, ti conviene studiarla un po se, come hai scritto, _devi_ fare questo programma.

Originariamente inviato da djpeppe

ora vorrei sapere se riuscite a portarla a javascript, grazie

Voglia di lavorare saltami addosso.

[djpeppe]

il codice di andbin è uno... io posto anche il codice javascript che ho provato a fare io, però ci deve essere un errore (penso sia di sintassi):

<body>
<script type="text/javascript" language="javascript">
var code=0;
var x3=0;
var x7=0;
var x5=0;
var x4=0;
var x9=0;
var ax3=0;
var ax7=0;
var ax5=0;
var ax4=0;
var ax9=0;
var bx3=0;
var bx7=0;
var bx5=0;
var bx4=0;
var bx9=0;
var cx3=0;
var cx7=0;
var cx5=0;
var cx4=0;
var cx9=0;
var dx3=0;
var dx7=0;
var dx5=0;
var dx4=0;
var dx9=0;
var p2=0;
var p3=0;
var p4=0;
var a=0;
for(x=0;x<1;x++) {
if(x3==0){code=3; x3=1;} else { 
	if(x7==0){code=7; x7=1;} else {
		if(x5==0){code=5; x5=1;} else {
			if(x4==0){code=4; x4=1;} else {
				if(x9==0){code=9; x9=1;} else {}}}}}

if(code!=3 && ax3==0){code=code*10+3; x3=1; p2=3;} else { 
	if(code!=7 && ax7==0){code=code*10+7; x7=1; p2=7;} else {
		if(code!=5 && ax5==0){code=code*10+5; x5=1; p2=5;} else {
			if(code!=4 && ax4==0){code=code*10+4; x4=1; p2=4;} else {
				if(code!=1 && ax9==0){code=code*10+9; x9=1; p2=9;} else {}}}}}
				
if((x3!=1 && p2!=3) && bx3==0){code=code*10+3; x3=1; p3=3;} else { 
	if((x7!=1 && p2!=7) && bx7==0){code=code*10+7; x7=1; p3=7;} else {
		if((x5!=1 && p2!=5) && bx5==0){code=code*10+5; x5=1; p3=5;} else {
			if((x4=1 && p2!=4) && bx4==0){code=code*10+4; x4=1; p3=4;} else {
				if((x9!=1 && p2!=9) && bx9==0){code=code*10+9; x9=1; p3=9;} else {}}}}}
				
if((x3!=1 && p2!=3) && (p3!=3 && cx3==0)){code=code*10+3; x3=1; p4=3;} else { 
	if((x7!=1 && p2!=7) && (p3!=7 && cx7==0)){code=code*10+7; x7=1; p4=7;} else {
		if((x5!=1 && p2!=5) && (p3!=5 && cx5==0)){code=code*10+5; x5=1; p4=5;} else {
			if((x4!=1 && p2!=4) && (p3!=4 && cx4==0)){code=code*10+4; x4=1; p4=4;} else {
				if((x9!=1 && p2!=9) && (p3!=9 && cx9==0)){code=code*10+9; x9=1; p4=9;} else {}}}}}

if((x3!=1 && p2!=3) && (p3!=3 && p4!=3) && dx3==0){code=code*10+3; x3=1;} else { 
	if((x7!=1 && p2!=7) && (p3!=7 && p4!=7) && dx7==0){code=code*10+7; x7=1;} else {
		if((x5!=1 && p2!=5) && (p3!=5 && p4!=5) && dx5==0){code=code*10+5; x5=1;} else {
			if((x4!=1 && p2!=4) && (p3!=4 && p4!=4) && dx4==0){code=code*10+4; x4=1;} else {
				if((x9!=1 && p2!=9) && (p3!=9 && p4!=9) && dx9==0){code=code*10+9; x9=1;} else {}}}}}


document.write("<a href=http://www.hwupgrade.it/");
document.write(code);
document.write(".html>");
document.write(code);
document.write("<\/a><br />");
if(code!=94573){x--; a++;}
if(a==100){x--;}

</script>
</body>

non ho incluso gli altri tag dell'html ma sono giusti al 100%

[suppaman]

Non conosco js, il codice mi sembra un mattone abbastanza illegibile.

Tra l'altro a che pro scrivere:

for(x=0;x<1;x++) {

?

[djpeppe]

bè lo so che non ha senso ma l'avevo messo perchè in effetti c'è bisogno di fare le istruzioni più volte ma non sò quante. Volevo mettere alla fine del codice questa scitta:

if(code==****){}else{x--}

dove ***** sta per l'ultimo numero che viene elaborato.
lo potrest controllare? grazie