none
Algoritmo para obter combinações RRS feed

  • 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 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...

     

     

     

     

    terça-feira, 27 de janeiro de 2009 14:51

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
    sexta-feira, 13 de março de 2009 08:22

Todas as Respostas

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

     

    Abraços a todos..

     

    quinta-feira, 29 de janeiro de 2009 10:05
  • 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...
    segunda-feira, 2 de fevereiro de 2009 14:58
  • Não vou fazer o algoritmo para você, mas aqui vai a dica:
    Isso é Análise Combinatória. Já estudou sobre o assunto?
    Wikipedia
    • Editado JobaDiniz quinta-feira, 5 de fevereiro de 2009 21:24 link
    quinta-feira, 5 de fevereiro de 2009 21:21
  • 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...

    segunda-feira, 9 de março de 2009 15:42
  • 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
    quinta-feira, 12 de março de 2009 16:50
  • 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
    sexta-feira, 13 de março de 2009 02:44
  • 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
    sexta-feira, 13 de março de 2009 08:22
  • 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
    sexta-feira, 13 de março de 2009 15:41
  • E ai Fabio, conseguiu resolver o problema?
    Rafael Medeiros
    segunda-feira, 16 de março de 2009 22:56
  • 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

    sexta-feira, 19 de junho de 2009 16:06
  • 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
    terça-feira, 11 de abril de 2017 21:30