Gerando Combinações Sem Repetição Pela Contagem Binária Em C

Introdução

Em um post anterior eu falei sobre como gerar as permutações-r com repetição. Nesse post pretendo ensinar como gerar combinações sem repetição dos elementos de um grupo de entrada. A linguagem utilizada aqui será a C, mas os conceitos vistos aqui podem ser facilmente portados para qualquer outra linguagem.

Definições

Combinação: é o agrupamento de algum ou todos elementos de um conjunto com elementos distintos. A combinação dos elementos [1,2,3] gera os seguintes agrupamentos: [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]. Repare que a ordem dos elementos em cada agrupamento não é importante, logo mudar a ordem dos elementos não gera combinações diferentes.

Combinações-r: são todos os agrupamentos de tamanho r resultantes da combinação do grupo de entrada. No exemplo acima, a combinação-2 do grupo [1, 2, 3] forma os agrupamentos: [1, 2], [1, 3].

A quantidade de agrupamentos resultantes de uma combinação-r é:

n!/(n-r)!*r!

onde n é a quantidade de elementos e r é o tamanho de cada agrupamento.

A quantidade total, variando-se o r de 0 a n, é de:

Cn, 0 = n!/(n-0)!*0!
+
Cn, 1 = n!/(n-1)!*1!
+
Cn, 2 = n!/(n-2)!*2!
+
Cn, 3 = n!/(n-3)!*3!
+
...
+
Cn, r=n = n!/(n-n)!*n!
=
2^n

Exemplo:

para n= 5
C5, 0 = 1
+
C5, 1 = 5
+
C5, 2 = 10
+
C5, 3 = 10
+
C5, 4 = 5
+
C5, 5 = 1
=
Total: 1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5

O método

O método para gerar todas as combinações de um conjunto consiste em casar as posições dos bits 1 de um número natural com as posições dos elementos do conjunto dado. Após esse mapeamento de posições, uma combinação será gerada. Como cada número natural gera um sequência binária diferente de todos os outros números, então cada agrupamento será único, o que está de acordo com a definição da combinação (a ordem dos elementos não gera um novo agrupamento).

Considere o número 3 em binário, 101. Se pensarmos que cada bit 1 ativa uma posição em específico, então as posições 0 (a primeira da direita para esquerda) e 2 foram selecionadas. Se varrermos todos os números entre 00000(2) e 11111(2), estaremos gerando todas as combinações para os n=5 elementos de entrada. Cada vez que o número é incrementado, os bits 1’s variam de posição, gerando assim agrupamentos diferentes. Daí para se gerar combinações de qualquer conjunto, simplesmente usamos as posições ativadas pelo bit 1 para selecionar elementos desse conjunto.

Exemplo

Considere a string: “abcd”. A tarefa aqui será gerar todas as combinações desses caracteres. Repare que o r aqui é variável, não estamos interessados no tamanho dos agrupamentos, e sim, como gerar todos eles. Como a string tem tamanho n=4, precisaremos varrer todos os números entre 0000(2) e 1111(2).

A tabela abaixo exemplifica o método utilizado. A primeira coluna representa todos os números no intervalo [0000(2), 1111(2)]. Já a segunda coluna contém os caracteres da string “abcd” que foram ativados pelos bits 1’s do número da primeira coluna.

+-------------------+-----------------+
|Número em binário  |  Combinação     |
+-------------------+-----------------+
|       0000        |     ""          |
+-------------------+-----------------+
|       0001        |     {a}         |
+-------------------+-----------------+
|       0010        |     {b}         |
+-------------------+-----------------+
|       0011        |   {a, b}        |
+-------------------+-----------------+
|       0100        |     {c}         |
+-------------------+-----------------+
|       0101        |   {a, c}        |
+-------------------+-----------------+
|       0110        |   {b, c}        |
+-------------------+-----------------+
|       0111        |  {a, b, c}      |
+-------------------+-----------------+
|       1000        |     {d}         |
+-------------------+-----------------+
|       1001        |   {a, d}        |
+-------------------+-----------------+
|       1010        |   {b, d}        |
+-------------------+-----------------+
|       1011        |  {a, b, d}      |
+-------------------+-----------------+
|       1100        |   {c, d}        |
+-------------------+-----------------+
|       1101        |  {a, c, d}      |
+-------------------+-----------------+
|       1110        |  {b, c, d}      |
+-------------------+-----------------+
|       1111        |  {a, b, c, d}   |
+-------------------+-----------------+

Repare que o mapeamento acontece da direita para a esquerda. Os bits menos significativos mapeiam os elementos iniciais da entrada. (ex: 0001 ativa o {a} e não o {d})

Código para gerar todas as combinações

Abaixo um código que gera todas as combinações dos caracteres de uma string de entrada.

/*
 * [comb.c]
 * Programa que gera todas as combinações dos caracteres
 * de uma string de entrada.
 *
 * [Autor]
 * Marcos Paulo Ferreir (Daemonio)
 * undefinido gmail com
 * https://daemoniolabs.wordpress.com/
 *
 * [Uso]
 * $ gcc -o comb comb.c
 * $ echo 'abcd' | ./comb
 *
 * Versão 1.0 by daemonio @ Thu Feb 17 08:17:31 BRST 2011
 *
 */
#include <stdio.h>
#include <string.h>

/* Tamanho máximo da entrada */
#define MAX_INPUT 31

int main() {
    unsigned MAX, MASK, NUM ;
    int i, j ;
    /* Armazena a string de entrada. */
    char input[MAX_INPUT] ;
    /* Armazena cada combinação. */
    char str[MAX_INPUT] ;

    printf("Digite o grupo inicial: ") ;
    scanf("%s", input) ;

    /* Manda o bit 1 para a n-ésima posição.
     * Os bits são invertidos para que a posição n
     * esteja com o bit zero, a fim de marcar
     * o final do processo.
     */
    MAX = ~(1 << strlen(input)) ;

    /* Primeiro número é o 1. */
    NUM = 1;

    putchar('\n') ;

    /* Quando o número alcançar MAX, o loop
     * será encerrado.
     */
    while ( MAX & NUM ) {
        MASK = 1 ;
        i = j = 0 ;

        while ( MAX & MASK ) {
            /* Verdadeiro se NUM tem um bit 1
             * na posição indicada por MASK. */
            if ( NUM & MASK ) {
                /* Gera a combinação em str. */
                str[i] = input[j] ;
                i++ ;
            }
            j++ ;
            /* Desloca a máscara */
            MASK = MASK << 1 ;
        }

        str[i]=0 ;
        printf("%s\n", str) ;

        NUM++ ;
    }

    return 0;
}

Exemplo de execução

Primeiro compilamos o programa:

$ gcc -o comb comb.c

em seguida um exemplo de execução:

$ ./comb
Digite o grupo inicial: 12345
1
2
12
3
13
23
123
4
14
24
124
34
134
234
1234
5
15
25
125
35
135
235
1235
45
145
245
1245
345
1345
2345
12345

Explicação do código

1)

#define MAX_INPUT 31
...
...
    MAX = ~(1 << strlen(input)) ;

    NUM = 1;
    putchar('\n') ;

    while ( MAX & NUM ) {

Essa operação AND diz quando o processo todo chegou ao fim. Como sabemos, a quantidade final de combinações é de 2^n, sendo n a quantidade de elementos. Uma maneira mais fácil de calcular 2^n, sem usar funções como pow(), é deslocando o bit 1 para a posição n de um número inteiro. Após o deslocamento, invertemos os bits por comodidade, pois é mais fácil entender que, quando NUM estiver com o bit da posição n ligado, o processo deve ser terminado. O problema disso é que o tamanho da entrada é prejudicado, sendo que ela deve ter no máximo 31 caracteres (considerando uma máquina 32 bits). Se você precisa que a entrada seja maior que 31 (o 32o bit será usado para o teste), tente um long long int ou simplesmente implemente o problema de outra maneira (ex: usando big nums).

2)

        MASK = 1 ;
        i = j = 0 ;

        while ( MAX & MASK ) {
            if ( NUM & MASK ) {
                str[i] = input[j] ;
                i++ ;
            }
            j++ ;
            MASK = MASK << 1 ;
        }

Como verificar quais bits estão ativados em determinado número? A única maneira possível é iterando, e é isso que o while faz. A variável MASK se inicia com valor 1, e a cada iteração, esse bit 1 vai sendo deslocado para uma posição à esquerda. Em seguida, na condição do loop, um AND é feito com as variáveis MAX e MASK para testar se o processo chegou ao fim. Repare que o loop termina quando o único bit ativo de MASK alcançar a posição do único bit vazio de MAX.

O if testa se o bit correspondente de MASK está ativo em NUM. Se sim, então devemos gerar uma combinação, utilizando as variáveis i e j como índices dos vetores str (resultado) e input (string de entrada).

3)

        str[i]=0 ;
        printf("%s\n", str) ;

Mostra o resultado na tela.

Gerando combinações-r

O código anterior gera todo tipo de agrupamento, mesmo aquelas com diferente quantidade elementos. Nessa parte iremos ver como gerar as combinações-r de um conjunto. A diferença agora é que um r será dado para indicar a quantidade de elementos de cada agrupamento.

Não tem mistério algum. O valor de r nos diz a quantidade exata de bits 1 que se deve ter no número NUM. O que vai mudar em relação ao código anterior é que agora teremos um loop para contar quantos bits 1 estão ativados no número. De posse dessa quantidade, iremos comparar essa quantidade com o r dado, e se forem iguais, uma combinação-r será gerada.

/*
 * [combr.c]
 * Programa que gera combinações de tamanho r de
 * todos caracteres de uma string de entrada.
 *
 * [Autor]
 * Marcos Paulo Ferreira (Daemonio)
 * undefinido gmail com
 *
 * [Uso]
 * $ gcc -o combr combr.c
 * $ ./combr
 *   abcd <-- digite a string
 *   3    <-- digite o r
 *
 * Versão 1.0 by daemonio @ Thu Feb 17 08:17:31 BRST 2011
 *
 */

#include <stdio.h>
#include <string.h>

/* Tamanho máximo da entrada */
#define MAX_INPUT 31

int main() {
    unsigned MAX, MASK, NUM ;
    int i, j, r, k ;
    /* Armazena a string de entrada. */
    char input[MAX_INPUT] ;
    /* Armazena cada combinação. */
    char str[MAX_INPUT] ;

    printf("Digite o grupo inicial: ") ;
    scanf("%s", input) ;

    printf("Digite o r: ") ;
    scanf("%d", &r) ;

    /* Manda o bit 1 para a n-ésima posição.
     * Os bits são invertidos para que a posição n
     * esteja com o bit zero, a fim de marcar
     * o final do processo.
     */
    MAX = ~(1 << strlen(input)) ;

    /* Primeiro número é o 1. */
    NUM = 1;

    putchar('\n') ;

    /* Quando o número alcançar MAX, o loop
     * será encerrado.
     */
    while ( MAX & NUM ) {
        /* Conta os bits 1's. */
        MASK = 1 ;
        k = 0 ;
        while ( MAX & MASK ) {
            if ( NUM & MASK ) k++ ;
            MASK = MASK << 1 ;
        }

        /* Monta o resultado somente se
         * a quantidade de bits k é igual
         * a r. */
        if ( k == r ) {
            MASK = 1 ;
            i = j = 0 ;

            while ( MAX & MASK ) {
                /* Verdadeiro se NUM tem um bit 1
                 * na posição indicada por MASK. */
                if ( NUM & MASK ) {
                    /* Gera a combinação em str */
                    str[i] = input[j] ;
                    i++ ;
                }
                j++ ;
                /* Desloca a máscara */
                MASK = MASK << 1 ;
            }

            str[i]=0 ;
            printf("%s\n", str) ;
        }

        NUM++ ;
    }

    return 0;
}

Exemplo de execução

$ gcc -o combr combr.c
$ ./combr
Digite o grupo inicial: 12345
Digite o r: 3
123
124
134
234
125
135
235
145
245
345

Explicação do código

1)

    while ( MAX & NUM ) {
        MASK = 1 ;
        k = 0 ;
        while ( MAX & MASK ) {
            if ( NUM & MASK ) k++ ;
            MASK = MASK << 1 ;
        }

        if ( k == r ) {

A única parte diferente é essa. Conta-se quantos bits estão ativos no número e armazena essa quantidade em k. Em seguida, compare-se k com r, e se forem iguais, gera-se um novo agrupamento.

Conclusão

Mais um método simples para resolver problemas aparentemente complicados. O único problema aqui é a limitação da entrada que depende da quantidade de bits do inteiro da máquina. Acredito que isso não seja um grande problema para a maioria, porque o máximo de 31 bits para a entrada é possível gerar muitas combinações (para ser exato: 2.147.483.648).

Referências

[1] All Combinations Without Repetitions by phoxis (Acessado em: Julho/2012)
http://phoxis.org/2009/10/13/allcombgen

[2] Licença dos códigos postados, a pedido do phoxis (Acessado em: Julho/2012)
http://phoxis.org/about/#license

52 pensamentos sobre “Gerando Combinações Sem Repetição Pela Contagem Binária Em C

  1. Pingback: Gerando Combinações Usando Java | Daemonio Labs

    • Olá Rafael,
      Creio que seja possível sim, mas não vejo vantagem de aplicar esse método recursivamente, pois a principal vantagem dele é a sua implementação iterativa.

      Para tornar os códigos recursivos você poderia substituir o `while’ por uma função recursiva que “simula” um loop (a cada chamada incrementa o valor de `NUM’). Mas isso não seria de fato recursão por fugir um pouco da definição.

      Há alguns métodos para gerar combinações que são recursivos por natureza e acho que são esses que você deveria dar uma olhada.
      Vi alguns deles pesquisando no google, mas no momento estou sem os links aqui. Se eu encontrá-los irei postá-los aqui para que você ou
      outra pessoa interessada possa fazer uma consulta.

      Obrigado pelo feedback,
      Daemonio.

  2. Muito obrigado novamente por me responder Daemonio!! Infelizmente eu não sei java, rsrs não to com muita sorte mesmo. Mas vou ver se consigo portar a função para C. Quando puder, poste o programa em C aqui!
    Obrigado novamente.
    Abraço.

    • Fala aí Rafael,

      Portei o código para C e está no link abaixo:

      http://pastebin.com/yHhgfVZS

      No fonte há uma pequena explicação de como a recursão funciona, mas para entender melhor é preciso fazer algumas anotações em papel para ver como que a pilha de recursão está sendo montada.

      Qualquer dúvida pode postar aqui.

      Daemonio
      t+

  3. estou a obter erro na linha 26 (vetor_tesouros[i] = abs(random()) % 500;)

    eu estou a usar code_blocks como IDE

    será por causa disso?

    eu já tinha tentado iniciar uma versão simples
    http://aed-fac.blogspot.pt/2013/03/tp1-desenvolvimento.html
    mas ai quando fui para a parte de colocar primeiro maior valor para o amigo 1 e segundo maior valores para o amigo 2 engasguei.

    tem como adaptar a sua versão para correr no code_blocks?

    porque usa na main os argumentos: int argc, char **argv ?

    • Olá Leonardo,

      gerar todas as combinações é o mesmo que listar todos os subconjuntos de um conjunto. O conjunto que contém todos os subconjuntos é chamado de conjunto potência e sua cardinalidade é 2^n, e para gerá-lo, podemos usar o algoritmo desse post.

      Então todo o problema que pode ser modelado por teoria de conjuntos e que em algum momento seja necessário listar os subconjuntos, esse algoritmo se tornará muito útil por ser bastante rápido e fácil de implementar.

      Abraços

    • Felipe, você precisará de um compilador. Se você estiver no Windows, baixe o Dev-cpp que ele contém um compilador como também um interface em que você pode digitar/colar o código.

      Veja na Internet algum tutorial de Dev-cpp. É fácil.

      Abraços

  4. amigo, como eu não sei nada de linguagem de programação, e preciso fazer um programa inicialmente simples, comecei a ver tutoriais e videos do access.. fiz o programa todo, mas travei na hora de gerar essas combinações.. sera que eu consigo utilizar esse seu método no excel? desculpe a ignorancia!

  5. Pingback: Gerando Combinações Iterativamente Usando Pilhas em C – Daemonio Labs

  6. Olá, eu gostaria de colocar combinações(12,7) mas não sei como inserir numeros de 2 caracteres ser lido como um numero de caracter só, tentei usar letras mas não funcionou corretamente

  7. Olá Daemonio, então existe a possibilidade de tentar resolver esse pequeno problema…A combinação e a permutação ja fizemos com o seu exemplo so faltam os arranjos e esses tem que compilar em um só programa.

    1. Este trabalho é parte da avaliação da disciplina Probabilidade e Estatística Aplicada I, conforme o
    critério de avaliação divulgado no plano de ensino.
    2. O prazo de entrega deste trabalho é 28/05 até 23:55 através da página da disciplina no moodle.
    3. Entregas após o prazo serão penalizadas com desconto cumulativo de 2,5 pontos por dia de atraso.
    4. O trabalho deve ser um código em C e admitir compilação através do CodeBlocks na plataforma
    Windows, sem alterações e sem erros. No caso de necessitar de bibliotecas específicas, as
    informações necessárias sobre onde conseguir e como instalar devem estar devidamente
    documentadas no próprio código.
    5. É necessário indentar o código, com nomes de variáveis simples e significativos e devidamente
    comentado.
    6. O trabalho pode ser feito em grupos de até 3 alunos, cujos nomes devem constar no início do código,
    sendo que não serão aceitas inclusões de nomes após a entrega.
    Cenário:
    As fórmulas para o cálculo de permutações, arranjos e combinações são simples e fáceis de implementar,
    porém, na maior parte das vezes, estamos interessados no conjunto dos resultados, ou seja, na sequência de
    de permutações, arranjos e combinações.
    Elabore um programa em C que leia um conjunto de símbolos (letras e números) sem repetições com no
    máximo 10 elementos via teclado, calcule a quantidade e liste:
    • Permutações
    • Arranjos
    • Combinações
    dos elementos do conjunto lido.

  8. Olá Fábio,

    aqui no blog temos a seguinte postagem:

    https://daemoniolabs.wordpress.com/2011/02/11/gerando-permutacoes-r-com-repeticao-em-c/

    O algoritmo gera Permutações e Arranjos. Aqui considero as permutações como os agrupamentos formados com todos os elementos. Os arranjos, ou permutações r, são agrupamentos de tamanho r com todos os elementos. O mesmo algoritmo gera os dois tipos, basta setar o tamanho de r.

    A formula da permutação é: r!
    e do Arranjo (ou permutação-r) é: Anr, = n! / (n – r)!

    se faço r=n (agrupamentos de n elementos) então a formula do Arranjo vira a da Permutação.

    Acredito que seja isso que você quer. Então basta olhar o algoritmo, fixar r=n para gerar permutações e não fixar o r para gerar Arranjos.

    Abraços

  9. Me desculpe, mas esse programa é uma porcaria. Primeiro que ele não aceita mais de um algarismo e segundo que ele não mostra todos os resultados, pois os últimos sobrescrevem os primeiros.
    Suas respostas às dúvidas das pessoas são ridículas e com certeza não os ajudou. Peço que tire essa porcaria da internet, visto que é um insulto às pessoas que realmente trabalham com isso e entendem de programação.
    Grato.

    • Olá,

      aceitei o comentário simplesmente porque outras pessoas podem estar passando por algo parecido.

      Em todos os exemplos eu usei a função scanf() para ler a string de entrada. Se você tentou passar os elementos do conjunto separados por espaço então a função lerá somente o primeiro elemento já que ela delimita a entrada por espaços em branco. Você, programador experiente, deveria saber disso.

      O código em si não é o mais importante, mas sim o método, que poderá ser aplicado em qualquer linguagem de programação. Considerei que cada caractere da string de entrada é um elemento por facilitar a escrita do código. Isso é, “12345” tem 5 elementos. Digitar “1 2 3 4 5” é um erro, pois somente resulta na leitura do primeiro “algarismo”, o “1”.

      Se esse não for o problema, responda de forma construtiva para que a dúvida fique clara.

      Abraços

  10. Caro Daemonio,
    Tentei executar este teu código para uma Combinacao-r de (60,6).
    Aplicando a fórmula C(60,6) = 60! / [(60 – 6)! X (6!)], ao invés de gerar 50.063.860 combinações, a sua implementação gerou 376.740 combinações.
    Por que? Há alguma explicação para isto, ou há alguma falha no código ?

    • Caro Givaldo,

      essa falha ocorre porque o algoritmo é limitado ao tamanho da palavra. Provavelmente você usou um int de 32 bits, e assim o tamanho máximo deve ser 31. O valor 60 estoura o int e o resultado fica não definido.

      Esse problema eu explico na conclusão:

      “O único problema aqui é a limitação da entrada que depende da quantidade de bits do inteiro da máquina.”

      Tente usar um “long long int” para as variáveis: MAX, MASK, NUM.

      Isso te dará uma palavra de 64 bits, que aceitará a entrada 60. Não esqueça de mudar também o valor de MAX_INPUT para 63.

      Antes de tudo, faça um printf no sizeof(int) para ver qual o tamanho da palavra. Se for 32, o erro é devido a isso.

      Abraços

      • A seguir as modificações para aceitar entradas de tamanho entre 0 e 63:

        1) incluir inttype.h
        2) #define MAX_INPUT 63
        3) Declarar como: uint64_t MAX, MASK, NUM ;
        4) Trocar por: MAX = ~((uint64_t)1 << strlen(input)) ;

        Se input tiver tamanho 60 então MAX = ~(1<<60). Esse número em decimal é: 17293822569102704639.

        Para verificar se é esse número mesmo em MAX, faça um: printf("Valor de MAX: %"PRId64, MAX) ;

        Coloquei no pastebin o código modificado:

        http://pastebin.com/vqykf8YE

        Para saber mais sobre o tipo uint64_t e o printf com PRId64, visite:

        http://stackoverflow.com/questions/2844/how-do-you-printf-an-unsigned-long-long-int

        É melhor uint64_t do que "long long" para se ter mais compatibilidade.

        Abraços

      • Caro Daemonio,
        Te mandei o questionamento nesta postagem do código em C, mas na verdade seria pro código Java, no outro tópico.
        Vou tentar aplicar as modificações que você me orientou, mas como você postou as modificações em código C, terias como mandar as modificação em Java também, pois como nunca trabalhei com bits diretamente, não tenho conhecimento neste assunto. Ex.: o tipo “uint64_t”, qual seria em java? Se puderes me ajudar nesse sentido, ficaria muito grato.

        Abraços,
        Givaldo.

  11. Olá Daemonio, usei parte de seu código em um projeto que estou desenvolvendo. O código pega arquivos .txt e os combina criando novos .txt de acordo com as combinações dos arquivos iniciais. No entanto a parte de geração das combinações falha quando envolvida com o código inteiro, mas quando executada em separado funciona perfeitamente. Você tem alguma ideia de qual pode ser o problema?

    • Olá Rodrigo,

      tem como me enviar o código? Qualquer coisa use o pastebin.com.

      Em todo caso, a nova combinação estará pronta na linha do printf:

      printf(“%s\n”, str) ;

      seja lá qual for sua intenção, é a partir dessa linha que você faz o uso da combinação. Sem ver o código fica difícil, se ele não for muito complexo, ficarei feliz em te ajudar.

      Abraços

  12. eae Daemonio
    tudo tranquilo?
    hein como que faço pra ele mostrar combinações de numeros tipo 06, 10, 12 , 14, 16, 18, 20, 22, pra mostrar as combinações possiveis de somente 5 ou 6 numeros destes, porque quando se usa virgula para separa-los, o resultado vira uma mistura que não da pra entender, vale dizer que eu não entendo nada desse programa kkkk
    se puder me ajudar agradeço
    vlw

    • Fala Kleber, td blz?

      No caso de números, você tem que trocar o vetor de string “char str[]” para um de números: int numeros[]={6,10,12,14,…}.

      Em vez de mapear em um caractere, deve ser feito um mapeamento no vetor de inteiros.

      Agora são 04:00 da manhã :D, no fim do dia eu posto um código, pode ser?

      Abraços

      • bom se vc puder me passar o código eu lhe agradeço muito kk
        o intuito do uso desse codigo é para o uso em loterias :)
        ele é perfeito pra isso!!! só mais uma duvida então : para copiar os numeros que ele demonstra na tela? :/

    • http://pastebin.com/3EVDU6ME

      Coloquei os números em um vetor fixo (int input[]). O máximo possível de números é 31, pois esse é o tamanho do int comum (em bits).

      As combinações estão armazenadas no vetor int str[].

      Para o esquema da loteria é melhor usar um loop para preencher o vetor de entrada. Caso precise de ajuda só postar.

      Abraços

  13. Gostaria de ter um programa que combinasse 5 valores fixos para dar um sexto valor. Objectivo: Tenho uma caixa grande com 10 metros cubicos e tenho 5 caixas mais pequenas com 1, 2, 3, 4 e 5 metros cubicos cada. Quero saber para alem de quantas combinacoes possiveis como e constituida cada combinacao (5+5 ou 2+3+5 ou 1+2+3+4, etc), para que as caixas pequenas caibam dentro da grande.

    • Olá,

      acho que a maneira mais fácil é gerar todas as combinações e para cada uma, usando comandos externos do linux, realizar a soma e verificar quais delas são menores ou iguais a 10.

      $ echo ‘12345’ | ./comb | sed ‘1d’ > saida.txt
      $ paste -d ‘:’ saida.txt <(sed 's/./&+/g;s/.$//' saida.txt | bc) | grep '10$'
      1234:10
      235:10
      145:10

      Isso é: 1+2+3+4 = 10, o mesmo para 2+3+5 e 1+4+5.

      Se desejar as menores que 10, é só mudar o filtro do grep ou usar o awk por possuir expressões matemáticas embutidas.

      Abraços

  14. voce vende um código desse?

    1)Dados os numeros inteiros de 1 a 25. Fazer um programa em c que gerá uma lista com os 25C15 =3.268.760 resultados possiveis.(25C15 combinação simples sem repetição de 25 elementos tomados 15 a 15) .
    Exemplo de saida

    listas de combinações 25C15
    resultado 1 ->12 10 15 18 02 03 25 04 07 11 17 16 09 01 24
    resultado 2-> …

    resultado 3,268,760->…..

    quando tento fazer 3.268.760 vetores com 15

    • Não entendi muito bem, temo como explicar melhor?


      25C15 combinação simples sem repetição de 25 elementos tomados 15 a 15

      Pelo que entendi, é só usar o código da postagem e usar esses 25 elementos como entrada e setar r=15. Se os elementos forem números, basta é só passar uma string de tamanho 25 com caracteres únicos e depois mapear cada caractere em um número.

      Execute o programa como:

      “abcdefghijklmnopqrstuvwxy” e passar r=15

      depois mapeie cada letra em um número (é preciso modificar o código, mas é facil):

      Exemplo:
      a -> 1
      b -> 2
      c -> 3

      y -> 25

      • aeee valeu!Nossa assim fica muito mais fácil mesmo deu certo!Demorou 7262.302 segundos para imprimir no .txt os 3268760 combinações.Valeu pela a ajuda muito bom esse site!

  15. Boa noite, gostei muito do código, estou curioso a respeito de um código que imprima todas as sequências possíveis de um dado vetor, se souber de algo, let me know, Valeus

  16. Ola amigo, curti muito esse seu algoritmo, e pretendia usar ele, no entanto ele não abrange todas as possibilidades. Por exemplo, ele gera o arranjo “1 2” mas não gera “2 1”.

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s