Usuário com melhor resposta
Algoritmo para obter combinações

Pergunta
-
Boa tarde a todos.
Bem, o cenário é o seguinte: Aplicação WindowsForms C# 2.0.
Possuo dois arrays e uma variável:
Code Snippetstring[] Letras = new string[5] { A, B, C, D, E }
int[] Numeros = new int[5] { 1, 2, 3, 4, 5}
int Membros = 6
A partir daí, preciso obter todas as combinações possíveis entre os membros de Letras e Numeros e cada combinação deve ter 6 membros na combinação, que é o valor de Membros e cada índice usado na combinação não pode se repetir. Seria Algo assim:
Combinação 1 = ABC123
Combinação 2 = ABC234
...
E assim por diante. O problema é que não faço idéia de como fazer isso. Pensei em fazer um loop e ir adicionando os valores em variáveis, gerar uma combinação deles, jogar num ArrayList e verificar se a combinação já está lá, se estiver, repete, se não faz outra combinação e insere, repeteindo o ciclo até obter todas as combinações possíveis.
Aguardo idéias dos amigos, pois meus cabelos já estão caindo (mais do que já caíram) tentando resolver isso, hehehe...
Abraços a todos...
Respostas
-
Fabio,
Achei um algoritmo que eu tinha feito ha algum tempo, adaptei pro que voce queria....ai vai...public partial class WordGenerator : Form { private List<string> m_Letras = new List<string>(); private List<string> m_Numeros = new List<string>(); public WordGenerator() { InitializeComponent(); Load += WordGenerator_Load; } void WordGenerator_Load(object sender, EventArgs e) { button1.Click += button1_Click; } void button1_Click(object sender, EventArgs e) { // Definicao dos Arrays string[] letras = new[] { "A", "B", "C", "D", "E" }; string[] numeros = new[] { "1", "2", "3", "4", "5" }; int tamanho = 3; m_Letras.Clear(); m_Numeros.Clear(); GeraNovaPalavra(m_Letras, letras, tamanho, string.Empty); GeraNovaPalavra(m_Numeros, numeros, tamanho, string.Empty); ConcatenaListas(); } private void GeraNovaPalavra(List<string> lista, string[] array, int tamanho, string palavraAtual) { string palavraCorrente = palavraAtual; for (int i = 0; i < array.Length; i++) { palavraCorrente += array[i]; if (palavraCorrente.Length >= tamanho) { lista.Add(palavraCorrente); palavraCorrente = palavraAtual; } else { GeraNovaPalavra(lista, array, tamanho, palavraCorrente); palavraCorrente = palavraAtual; } } } private void ConcatenaListas() { listBox1.Items.Clear(); foreach (string letra in m_Letras) { foreach (string numero in m_Numeros) { listBox1.Items.Add(string.Format("{0}{1}", letra, numero)); } } } }
Espero que ajude.
Rafael Medeiros- Marcado como Resposta Fabio Crash sexta-feira, 19 de junho de 2009 16:04
Todas as Respostas
-
-
-
JobaDiniz disse:Longe de mim querer que façam meu trabalho, só precisava de uma idéia de como começar.
Não vou fazer o algoritmo para você, mas aqui vai a dica:
Isso é Análise Combinatória. Já estudou sobre o assunto?
Wikipedia
Vou pesquisar sobre o assunto, obrigado pela dica.
Abraços a todos... -
Fabio,
Não sei se você já resolveu seu problema, mas eu já implementei algo parecido. No seu caso, tem algumas perguntas que você deveria fazer antes de começar a implementar:
1. O número de membros é o que determina quantos caracteres de cada array que vão ser usados?
Nesse seu caso o Membros igual a 6, quer dizer que são 3 letras e 3 números? Se Membros for 8, quer dizer 4 letras e 4 números? Se sim, e se o Membros for ímpar??
Recomendo você gerar duas listas independentes para as letras e para os números, e depois unir a combinação final.
Aqui vai mais ou menos a lógica que usei...
Imagine seu array de letras { A, B, C, D, E }, e imagine que você quer gerar combinações de 3 letras (entre parênteses você ver o índice das mesmas no array):
AAA (000)
AAB (001)
AAC (002)
AAD (003)
AAE (004)
ABA (010)
ABB (011)
ABC (012)
ABD (013)
ABE (014)
ACA (020)
ACB (021)
ACC (022)
ACD (023)
ACE (024)
ADA (030)
ADB (031)
ADC (032)
ADD (033)
ADE (034)
AEA (040)
AEB (041)
AEC (042)
AED (043)
AEE (044)
BAA (100)
.....
Então, você tem que criar um método recursivo, que vá incrementando do último índice para o primeiro, e montando as combinações.
Deu mais ou menos para ter uma idéia de como é?
Espero que sim.
Abraços.
Rafael Medeiros -
Ola Fabio, ta querendo inventar um novo algoritmo de Mp3...rs
Bom imagino que vc queira criar isso aleatoriamente, se sim:
Acho que este script ira te ajudar, depois basta concatenar os arrays e pronto vc tera oque precisa:
using System; class Program { static Random rand = new Random(); static void Main() { int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; RandomizeArray(ref array); foreach (int i in array) { Console.WriteLine(i); } Console.ReadLine(); } public static void RandomizeArray(ref int[] array) { int[] temp = new int[array.Length]; bool[] alreadyDrawn = new bool[array.Length];// all false int count = 0; int element = 0; int index = 0; while (count < array.Length) { index = rand.Next(0, array.Length); element = array[index]; if (!alreadyDrawn[index]) { temp[count++] = element; alreadyDrawn[index] = true; } } array = temp; } }
Att..
Nelson Borges - Analista de Sistemas -
Fabio,
Achei um algoritmo que eu tinha feito ha algum tempo, adaptei pro que voce queria....ai vai...public partial class WordGenerator : Form { private List<string> m_Letras = new List<string>(); private List<string> m_Numeros = new List<string>(); public WordGenerator() { InitializeComponent(); Load += WordGenerator_Load; } void WordGenerator_Load(object sender, EventArgs e) { button1.Click += button1_Click; } void button1_Click(object sender, EventArgs e) { // Definicao dos Arrays string[] letras = new[] { "A", "B", "C", "D", "E" }; string[] numeros = new[] { "1", "2", "3", "4", "5" }; int tamanho = 3; m_Letras.Clear(); m_Numeros.Clear(); GeraNovaPalavra(m_Letras, letras, tamanho, string.Empty); GeraNovaPalavra(m_Numeros, numeros, tamanho, string.Empty); ConcatenaListas(); } private void GeraNovaPalavra(List<string> lista, string[] array, int tamanho, string palavraAtual) { string palavraCorrente = palavraAtual; for (int i = 0; i < array.Length; i++) { palavraCorrente += array[i]; if (palavraCorrente.Length >= tamanho) { lista.Add(palavraCorrente); palavraCorrente = palavraAtual; } else { GeraNovaPalavra(lista, array, tamanho, palavraCorrente); palavraCorrente = palavraAtual; } } } private void ConcatenaListas() { listBox1.Items.Clear(); foreach (string letra in m_Letras) { foreach (string numero in m_Numeros) { listBox1.Items.Add(string.Format("{0}{1}", letra, numero)); } } } }
Espero que ajude.
Rafael Medeiros- Marcado como Resposta Fabio Crash sexta-feira, 19 de junho de 2009 16:04
-
-
-
Boa tarde, Rafael.
Desculpe a demora em responder, mas estive muito ocupado nos últimos meses...
Cara, obrigado pela ajuda! Seu algoritmo serviu exatamente para o que eu precisava. Só tive de fazer algumas modificações e adaptações, mas no geral ajudou e muito.
Miuto obrigado pela ajuda.
Abraços a todos os que participaram deste thread.
Fabio Crash -
Boa noite gente..
Preciso de um código de combinação.
Tenho 4 numeros: 2, 5, 6, 8 e preciso de um código pra encontrar todas as combinações possíveis.
Podem me ajudar... sou leigo ainda no assunto. rsrs.
- Editado Eudosan terça-feira, 11 de abril de 2017 21:30