Combinação Por Índice Lexicográfico

Esta calculadora online encontra combinação através do índice em conjunto ordenado lexicograficamente.

Esta página existe graças aos esforços das seguintes pessoas:

Timur

Timur

Julia Gomes

Criado: 2021-07-20 21:25:09, Ultima atualização: 2021-07-20 21:25:09

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.

PLANETCALC, Combinação Por Índice

Combinação Por Índice

Combinação
 
Número total de combinações
 

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

  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.

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

URL copiado para a área de transferência
PLANETCALC, Combinação Por Índice Lexicográfico

Comentários