Combinação Por Índice Lexicográfico
Esta calculadora online encontra combinação através do índice em conjunto ordenado lexicograficamente.

Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.
Em matemática, a ordem lexicográfica (também conhecida como ordem lexical, ordem do dicionário ou ordem alfabética) é uma forma como as sequências (ou seja, palavras) são ordenadas alfabeticamente com base na ordem alfabética de seus componentes (letras). Frequentemente é utilizada na combinatória para produzir todas as combinações possíveis - elas são geradas em ordem lexicográfica.
Suponhamos que temos um conjunto de 5 elementos { 0 1 2 3 4 } e queremos gerar todas as 3 combinações. Existem 10 combinações e aqui elas estão em ordem lexicográfica.
0: { 0 1 2 }
1: { 0 1 3 }
2: { 0 1 4 }
3: { 0 2 3 }
4: { 0 2 4 }
5: { 0 3 4 }
6: { 1 2 3 }
7: { 1 2 4 }
8: { 1 3 4 }
9: { 2 3 4 }
Se você deseja gerar todas as combinações possíveis em ordem lexicográfica, você pode utilizar a calculadora Combinatória. Gerador de combinações.
Sendo assim, esta calculadora produz uma combinação através de seu índice em uma lista ordenada lexicograficamente de todas as combinações. Claro, ela faz isso sem calcular todas as combinações por uma questão de eficiência. Você pode encontrar a descrição do algoritmo abaixo da calculadora.
Observação: o índice é baseado em ZERO.
Encontrando a combinação através de seu índice lexicográfico
Esta calculadora utiliza um algoritmo descrito por James McCaffrey1.
Vamos usar as seguintes notações e definições:
- n - número de elementos no conjunto, por exemplo, 5
- k - número de elementos em combinação, por exemplo, 3
- N - número total de combinações, por exemplo, 10
- índice de combinação na lista lexicográfica, baseado em zero, de 0 a N-1, por exemplo, 0 ... 9
- índice duplo - índice oposto, a soma do índice e seu oposto dá N-1, por exemplo, para o índice 1; o índice duplo é 8
Algoritmo
- Encontre índice duplo para determinado índice i calculando (N-1) - i
- Encontre o combinadic do índice duplo, consulte o Sistema de numeração combinatória
- Inverta cada coeficiente combinadic c calculando (n-1) - c
- Os coeficientes resultantes representam a combinação desejada.
-
James McCaffrey. Generating the mth Lexicographical Element of a Mathematical Combination (Gerando o mº Elemento Lexicográfico de uma Combinação Matemática). MSDN Magazine, Julho de 2004 ↩
Comentários