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:
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:
#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 )