jrestojeda wrote:Hola a todos...
Necesito armar un algoritmo que me devuelva todas las combinaciones posibles de una serie de letras formando combinaciones mayores o iguales a 3 caracteres.
Ejemplo tomando la palabra "ESTEBAN"
Obtener como resultado:
EST
ESTE
ESTEB
ESTEBAN
SET
SETB
SETBA
SETBAN
Etc, etc etc...
A alguien se le ocurre como encarar este algoritmo?
Desde ya muchas gracias.
Saludos,
From your posting, what you are looking for are not just combinations but all permutations of
( 3 of 7 ) + ( 4 of 7 ) + ( 5 of 7 ) + ( 6 of 7 ) + ( 7 of 7 ) characters.
If each character in the source string is unique, we get a total of 13,650 permutations (from 99 combinations).
Forumla:
- Code: Select all Expand view
fact(7)/fact(4) + fact(7)/fact(3) + fact(7)/fact(2) + fact(7) + fact(7) // --> 13,650
FACT(n) is a function in CTLIB, which gives factorial of n.
However the alphabet "E" is repeated twice resulting in some duplicate results. Ignoring such duplicates, we get 95 combinations finally resulting in 8,553 total permutations.
Program to generate all unique combinations and permutations:
- Code: Select all Expand view
#include "fivewin.ch"
static aPrm := {}
static aCmb := {}
static aResult := {}
function Main()
local cSrc := "ESTEBAN"
local n
for n := 3 to Len( cSrc )
Combinations( n, "", cSrc )
next
for n := 1 to Len( aCmb )
aPrm := {}
Permutations( "", aCmb[ n ] )
AMERGE( aResult, aPrm )
next
XBROWSER aCmb SHOW RECID TITLE "COMBINATIONS"
XBROWSER aResult SHOW RECID TITLE "PERMUTATIONS"
// ? fact(7)/fact(4) + fact(7)/fact(3) + fact(7)/fact(2) + fact(7) + fact(7)
return nil
function Combinations( r, cCmb, cSrc )
local nLen := Len( cSrc )
local n
if r == 0
if AScan( aCmb, cCmb ) == 0
AAdd( aCmb, cCmb )
endif
else
for n := 1 to ( nLen - r + 1 )
Combinations( r - 1, cCmb + SUBSTR( cSrc, n, 1 ), SUBSTR( cSrc, n + 1 ) )
next
endif
return nil
function Permutations( cLeft, cRight )
local nLen := Len( cRight )
local n
if nLen == 0
if AScan( aPrm, cLeft ) == 0
AAdd( aPrm, cLeft )
endif
else
for n := 1 to nLen
Permutations( cLeft + SUBSTR( cRight, n, 1 ), ;
Left( cRight, n - 1 ) + SubStr( cRight, n + 1 ) )
next
endif
return nil
So far, this is of mathematical interest.
But I am wondering what can be the practical use of this huge result-set.
Formulae of interest:
Total permutations of r out of n = n! / ( n - r )!
Total combinations of r out of n = n! / ( r! * ( n - r )! )
where n! is Factorial( n )