Rotina para array de numeros

Barata

I folded Myself
Boas!

Precisava que me dessem umas dicas de como codar uma rotina que permita testar todas as combinações entre elementos de um array.

Exemplo:

int array[5]={12, 23,45, 10, 9};

A rotina tem de todas as combinações possiveis destes 5 numeros.

Por exemplo: 23, 12, 9, 10, 45 .

Se não fui claro, não hesitem em colocar as vossas duvidas à cerca do problema.

Hugzz! ;)

PS- A linguagem é C, mas o que necessito mesmo é de um algoritmo e não do código em si.
 
Última edição:
Estas combinações são possiveis?
{ 12 }
{ 12 23 }
{ .........}
E
{ 23, 12, 9, 10, 45 } é diferente de:
{ 23, 12, 9, 45, 10 }

?
 
Karmack disse:
Estas combinações são possiveis?
{ 12 }
{ 12 23 }
{ .........}
E
{ 23, 12, 9, 10, 45 } é diferente de:
{ 23, 12, 9, 45, 10 }

?

As combinações geradas têm que ter sempre os 5 numeros.

Sim, { 23, 12, 9, 10, 45 } != { 23, 12, 9, 45, 10 }.

;)
 
ORa bem, não pensei que isto fosse dar tantos problemas de interpretação, mas aqui vai algo que decerto facilitará.

Isto é para um programa que estou a fazer para descobrir qual o menor caminho entre 40 cidades.

Decidi fazer isto recorrendo ao menor caminho entre blocos de 10 cidades.

Exemplo:

Caminho 1: {1,2,3,4,5,6,7,8,9,10} = 500km
!=
Caminho 2: {2,1,3,4,5,6,7,8,9,10}= 493km

Como é obvio já tenho função que me vai dar estas distancias. Isto foi apenas um exemplo. Cada numero representa uma cidade.
:(
 
Já ouviste falar do algoritmo de Dijkstra? Dado um ponto este calcula a menor distancia e os nós do caminho mais curto.
Investiga no wikipedia ou usa o google.
 
http://en.wikipedia.org/wiki/Dijkstra's_algorithm

Isto fazia parte da minha consulta para o exame de AED2, deu bastante jeito(tem implementações em C, C++ e Python, para dar ainda menos trabalho ;)).

Lembro-me também de um site que simulava (em applets de java) o funcionamento de vários algoritmos relacionados com grafos, aqueles de que o fap falou, por exemplo :) Se quiseres posso procurar-te isso.
 
isso é permutações
http://en.wikipedia.org/wiki/Permutation
têm lá no "permutation in computing" algoritmos para isso, lê.

entretanto toma já uma implmentação para vectores de inteiros com o exemplo que deste:

Código:
#include <stdlib.h>
#include <stdio.h>

void swap( int * array, int a, int b )
{
	int temp = array[a];
	array[a] = array[b];
	array[b] = temp;
}

int permute( int *  array, int size )
{
	int key = size - 1;
	int newkey = size - 1;

	while( (key > 0) && (array[key] <= array[key-1]) )
	{
		key--;
	}
	key--;

	if( key < 0 )
        return 0;

	newkey = size - 1;
	while( (newkey > key) && (array[newkey] <= array[key]) )
	{
		newkey--;
	}

	swap( array, key, newkey );

	size--;
	key++;

	while( size > key )
	{
		swap( array, size, key );
		key++;
		size--;
	}

	return 1;
}

int main( int argc, char *argv[] )
{
	int test_array[] = { 12, 23,45, 10, 9 };

	do  
	{
		printf( "%d  %d  %d  %d  %d\n", test_array[0], test_array[1], test_array[2], test_array[3], test_array[4] );
	}
	while( permute( test_array, 5 ) );
	
	return 0;
}
 
Back
Topo