Algoritmo para obter combinações

Question

Boa tarde a todos.

 

Bem, o cenário é o seguinte: Aplicação WindowsForms C# 2.0.

 

Possuo dois arrays e uma variável:

 

Code Snippet

string[] 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...

 

 

 

 

Answer 1

Ninguém, pessoal? Qualquer idéia serve...

 

Abraços a todos..

 

Answer 2

Nenhum dos colegas passou por nenhuma situação parecida? Preciso gerar números de série a partir disso... Qualquer ajuda é bem vinda...

Grato a todos...

Answer 3

Não vou fazer o algoritmo para você, mas aqui vai a dica:
Isso é Análise Combinatória. Já estudou sobre o assunto?
Wikipedia

Answer 4

JobaDiniz disse:

Não vou fazer o algoritmo para você, mas aqui vai a dica:
Isso é Análise Combinatória. Já estudou sobre o assunto?
Wikipedia

Longe de mim querer que façam meu trabalho, só precisava de uma idéia de como começar.

Vou pesquisar sobre o assunto, obrigado pela dica.

Abraços a todos...

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

Muito obrigado Rafael e Nelson!

Seus exemplos e dicas foram de grande ajuda. Agora já tenho por onde começar o trabalho.

Depois posto os resultados e marco como respondido.

Grato a todos pela atenção.

Att. Fabio Crash

Answer 9

E ai Fabio, conseguiu resolver o problema?

---

Rafael Medeiros

Answer 10

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

Answer 11

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.