Combinação Por Índice Lexicográfico

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.

Combinação Por Índice

Conjunto tamanho n

Combinação tamanho k

Índice lexicográfico

Calcular

Combinação

 

Número total de combinações

 

 Link  Salvar  Widget

Encontrando a combinação através de seu índice lexicográfico

Esta calculadora utiliza um algoritmo descrito por James McCaffrey¹.

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

1. Encontre índice duplo para determinado índice i calculando (N-1) - i
2. Encontre o combinadic do índice duplo, consulte o Sistema de numeração combinatória
3. Inverta cada coeficiente combinadic c calculando (n-1) - c
4. Os coeficientes resultantes representam a combinação desejada.