Jump to content

Combinações de inteiros sem repetição


wolfbuda
 Share

Recommended Posts

Bom dia,

Ando à procura da melhor forma de fazer um algoritmo que devolva todas as combinações possíveis, sem repetição, dado um conjunto de valores.

Por ex: dado o conjunto de três inteiros 1, 2, 3, devolver:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Obrigado.

Link to comment
Share on other sites

Isso não são combinações, são permutações.

O algoritmo mais "clássico" é o de trocas sucessivas, ficando as permutações listadas por ordem lexicográfica:

Dado um vector com a primeira permutação (isto é, com os elementos ordenados do menor para o maior), executar sucessivamente os seguintes passos:

1. Seja i o maior índice do vector onde v[ i ] < v[ i + 1 ] - se este índice não existir (isto é, a situação não ocorre no vector), estamos na última permutação, estando o vector com os elementos ordenados do maior para o menor;

2. Trocar os elementos nas posições v[ i ] e v[ i + 1 ];

3. Inverter os elementos nas posições superiores a i (o último passa para i + 1, o penúltimo para i + 2 e por aí fora);

4. Neste momento, temos a permutação seguinte à que começámos - imprimir, guardar, whatever e recomeçar estes passos.

Há outros algoritmos, incluindo alguns mais rápidos, mas acho que este é o mais simples de entender.

"Para desenhar um website, não tenho que saber distinguir server-side de client-side" - um membro do fórum que se auto-intitula webdesigner. Temo pelo futuro da web.

Link to comment
Share on other sites

Eu faria por recursividade, caso fosse o conjunto tivesse um número variável de inteiros, e com loops caso tivesse um número conhecido.

Basicamente, a função recursiva chama-se a si própria para cada elemento do set, passando a si própria um set com um elemento a menos e o set dos elementos "chamados". Quando o set estiver vazio, imprime os números percorridos. Esta técnica é uma variante de DFS.

Link to comment
Share on other sites

Concordo com o Cynary, eu faria por recursividade também.

Terias dois vectores, um para o conjunto permutado e outro para guardar os elementos que já estão utilizados. A cada chamada recursiva (dentro de um loop) verificavas se o elemento actual já foi usado, se sim então metes no vector se não continuas sem faz nada.

here since 2009

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.