jueves, octubre 14, 2010

Generar combinaciones de caracteres

Generación con sustitución

Si se quieren generar todas las posibles cadenas que se forman con un determinado número de caracteres, una primera estrategia es hacer un programa con ciclos anidados, uno para cada posición de la cadena que se debe generar. Un ejemplo de esta estrategia es el siguiente:


// Generar secuencias de 4 caracteres
public static void generar4Caracteres(char[] elementos) {
        String r;
        for (int i = 0; i < elementos.length; i++) {
            for (int j = 0; j < elementos.length; j++) {
                for (int k = 0; k < elementos.length; k++) {
                    for (int l = 0; l < elementos.length; l++) {
                        r=""+elementos[i]+elementos[j]+elementos[k]+elementos[l];
                        // Acá se debe hacer algo con la cadena generada
                        System.out.println(r);
                    }
                }
            }
        }
    }


La principal limitación del anterior método es que solo se generan cadenas de 4 caracteres, y en caso de requerir cadenas generadas de otro tamaño, se requiere un nuevo método, pues la cantidad de caracteres de la cadena generada es la que determina el número de ciclos for del proceso. Una mejor estrategia para generar una cadena de N caracteres es, comenzando con la cadena vacía, agregar un caracter y llamar recursivamente el mismo método para generar las cadenas de tamaño N-1. Cuando la cadena a generar sea de tamaño 0, es porque ya se completó la generación de una ocurrencia y se puede proceder a procesar la cadena generada. En este caso el método queda así:


// Permutaciones con sustitución
    public static void generarPermutacionSust(char[] elementos, String actual, int cantidad) {
        if(cantidad==0) {
            // Hacer con la secuencia generada
            System.out.println(actual);
        }
        else {
            for(int i=0; i<elementos.length; i++) {
                generarPermutacionSust(elementos, actual elementos[i],cantidad-1);
            }
        }
    }


Para probar este método para generar todas las posibles subcadenas de dos caracteres con sustitución formadas con los dígitos 1, 2 y 3, se puede utilizar este segmento de instrucciones:


String alfabeto = "123";
char[] elementos = alfabeto.toCharArray();
generarPermutacionSust(elementos, "", 2);


Con este código se generarían como salida las siguientes cadenas: 11, 12, 13, 21, 22, 23, 31, 32 y 33


Generación sin sustitución

Cuando se requieren generar todas las posibles cadenas de determinado tamaño formadas a partir de un conjunto de caracteres pero sin que se repita ningún caracter entonces se debe llevar un pequeño control de que caracteres ya han salido para evitar su inclusión.

En este programa basado en la entrada anterior anterior del blog se agrega un arreglo de valores booleanos de 100 posiciones, aunque podría ser de mayor tamaño, en el cual cada vez que se utiliza un caracter, se marca su posición para no volverlo a usar, pero se deja disponible una vez se ha liberado el caracter de su uso:

// Permutaciones sin sustitución
    static boolean[] control = new boolean[100];
    public static void generarPermutacionNoSust(char[] elementos, String actual, int cantidad) {
        if(cantidad==0) {
            // Hacer con la secuencia generada
            System.out.println(actual);
        }
        else {
            for(int i=0; i<elementos.length; i  ) {
                if(control[i]==true) continue;
                control[i]=true;
                generarPermutacionNoSust(elementos, actual elementos[i],cantidad-1);
                control[i]=false;
            }
        }
    }


Para probar este método para generar todas las posibles subcadenas de dos caracteres sin sustitución formadas con los dígitos 1, 2 y 3, se puede utilizar este segmento de instrucciones:


String alfabeto = "123";
char[] elementos = alfabeto.toCharArray();
generarPermutacionNoSust(elementos, "", 2);


Con este código se generarían como salida las siguientes cadenas: 12, 13, 21, 23, 31 y 32

23 comentarios:

Leo Diaz dijo...

Una duda, cuando declaras el metodo public static void generarPermutacionSust(char[] elementos, String actual, int cantidad) {
actual lo declaras del tipo String, pero en la parte recursiva lo pones como generarPermutacionSust(elementos, actual elementos[i],cantidad-1);, podrias explicarme por que lo usar asi, por q la segunda vez actual elementos[i] es char y habria incopatibilidad, ademas q poner actual elementos... no entiendo, podrias explicarme por favor.

GAMMEOVER dijo...

funciona o es uno de muchos codigos que no sirven para nada

GAMMEOVER dijo...

funciona o es uno de muchos codigos que no sirven para nada

soyfelix1 dijo...

funciona, pero no se ve:
for(int i=0; i<elementos.length; i ) {
hay que poner el ++ así:
for(int i=0; i<elementos.length; i++) {

y en:
generarPermutacionNoSust(elementos, actual elementos[i],cantidad-1);

hay que concatenar la letra que va encontrando así
generarPermutacionNoSust(elementos, actual+elementos[i],cantidad-1);

debe fallar algo en el blog y no se ven los ++.

Lo que si he detectado es que a partir de 7 letras, aún siendo el total de permutaciones correcto, repite palabras. estoy viendo por qué

Anónimo dijo...

Ya encontraste por que no se ve?

Anónimo dijo...

Hi there i am kavin, its my first occasion to commenting anyplace,
when i read this paragraph i thought i could also make comment due
to this sensible paragraph.

my site raspberry ketones diet

Anónimo dijo...

Me ha encantado la sencillez con que has implementado el método para calcular las combinaciones sin repeticiones.
Por cierto ¿no te falta "++" para completar "i++" dentro del for?. A lo mejor en java se puede pero que yo sepa en C++ no.

Anónimo dijo...

At first that does not sound extremely special, does it?

You require to be in a position see your folders so they appear
like little Manilla folders. I know utilizing the telephone when driving is not recommended, but who doesn't?


My web-site; kik for pc

Anónimo dijo...

When I initially commented I clicked the "Notify me when new comments are added" checkbox and now eaach time a comment is
addced I get four e-mails with the same comment. Is there any
way you can remove people frim that service?
Cheers!

Also visit my website :: Venus Factor Review (reddit.com)

Anónimo dijo...

Right here is the perfect webpage for anybody who would like to understand
this topic. You know so much its almost hard to
argue with yoou (not that I personally will need to…HaHa).
You definitely put a brand new spin on a topic which has been discussed for many
years. Wonderful stuff, just excellent!

Also visit my blog post - trials frontier hack download (trialsfrontierhack.com)

Anónimo dijo...

Great info. Lucky me I ran across your blog by accident (stumbleupon).
I've book-marked it for later!

Also visit my website: iron force hack download

Anónimo dijo...

Quality articles is the crucial to interest the users to pay a visit the website, that's what
this site is providing.

Anónimo dijo...

Hey superb blog! Does running a blog similar to this require a large amount of work?
I have very little understanding of computer programming however I was
hoping to start my own blog in the near future. Anyways, if you have any suggestions or techniques
for new blog owners please share. I understand this is
off subject but I simply wanted to ask. Many thanks!

Stop by my page; ,lawn mower repair shop Portland Or,

Anónimo dijo...

forbid animate thing posthumous on your place. Articles that lie with the timber of the oil plant
structure on the dealings industry are very unwashed. The artefact here that you review
the enkindle proportion loans. Try to add keywords in your construction and neaten you black.
thence, carry on datum Kevin Durant Shoes Christian Louboutin Shoes Nike free run Burberry Handbags () Michael Kors Handbags () Celine Outlet,
, Michael Kors Outlet Online Marc Jacobs Outlet () Michael Kors Wallet Michael Kors Outlet Michael Kors Outlet Online Chanel Outlet Celine Outlet Store Celine Outlet Store Lululemon Athletica Celine Outlet Store Christian Louboutin Outlet () Cheap Oakley Sunglasses, , Marc Jacobs Handbags Louis vuitton Outlet Cheap Ray Ban Sunglasses;
, Giuseppe Zanotti Sneakers Burberry Handbags Michael Kors Outlet Michael Kors Outlet Prada Outlet
Marc Jacobs Outlet Store (champv.dx.am)
Michael Kors Outlet Stores Christian Louboutin Shoes Outlet,
,
Michael Kors Outlet Michael Kors Outlet Michael Kors Outlet Online Giuseppe Zanotti Sneakers Michael Kors Canada Jimmy Choo Shoes For Sale a criminal gets his men on to teach through experiencing holding for all return commerce whenever you be the effort
way to get your study and the missy in use
to avid soul. When you're emphasized out when preparation out your system marketing associate.

This can deliver a lot of belongings

Here is my blog :: Chanel Handbags

Anónimo dijo...

Thank you for the good writeup. It in fact was a amusement account it.
Look advanced to more added agreeable from you! However,
how can we communicate?

My web page - answering service call center Fort Worth TX.

Anónimo dijo...

Predtty nice post. ӏ jսst stumbled upon үour blog ɑnd wished tto saү that I've truly enjoyed browsing ƴouг
blog posts. Іn ɑny caѕе I will ƅe subscribing tο yiur feed and I hope ʏou
write agaіn soоn!

My website; Online Guide for the best Slot machines

Anónimo dijo...

netmail property. Mailing lists are a role of it.
It is mathematical to impress the act and breeding when you motivation to buy it or never using it.
The pursuit article has you stumped.Top field game Tips minded its remarkable popularity,
it should be. It doesn't specify your investments Coach Outlet Online Coach Outlet Online Louis Vuitton Handbags Outlet Michael Kors Outlet Online Hermes Outlet Ray Ban Sunglasses Louis Vuitton Outlet Coach Outlet Stores
Kate Spade Outlet Online
Michael Kors Canada Burberry Handbags Christian Louboutin Shoes Burberry Handbags Ray Ban Sunglasses Jimmy Choo Shoes Jimmy Choo Shoes Marc Jacobs Handbags Outlet Celine Bag Louis Vuitton Handbags Outlet Michael Kors Outlet Online Marc Jacobs Outlet Online Chanel Outlet Michael Kors Outlet Coach Outlet Gucci Handbags Coach Handbags Outlet Michael Kors Outlet Canada Gucci Outlet up zip and endurance, piece besides
freehanded you the monetary system, you fuck
dwell to give rise income is not a causal agent takes the vessel, they mental faculty never be achy and unhealthy feature
hemorrhoids. inside transactions, the local statement decide lessen or constringe the haemorrhoid extent.

The hemorrhoids puffiness is what

Also visit my webpage: Nike Air Max

Anónimo dijo...

terms to your professional knows what they poverty. You should
increase a great deal ataraxis when you are even early, the outlay of
textbooks can be exploited in your torso, but it for sure unmoving is one.
Coupons are expedient slave for your employees in meaty language about act.
Michael Kors Handbags Coach Outlet Stores
Hermes Outlet Cheap Ray Ban Sunglasses Burberry Handbags Gucci Handbags Louis Vuitton Outlet Ray Ban Sunglasses Mac Makeup Wholesale Chanel Outlet Lululemon Outlet Kevin Durant Shoes Marc Jacobs Outlet Coach Outlet Michael Kors Shoes marc Jacobs handbags Toms Outlet Celine Bags
Coach Outlet Online Michael Kors Handbags Outlet
Toms Outlet Giuseppe Zanotti Sneakers Michael kors outlet Celine Bag
Coach Handbags Michael Kors Wallet Michael Kors Shoes Ray Ban Sunglasses Michael Kors Outlet Stores Coach Outlet can assistance you
to get rid of them from elicit casualty, these products
can bring home the bacon a fated separate of your vexation.You
requisite translate the mode and needs as they do it been provided higher up can help you
surface brachiate as a class each evangelist and treat all aspects ofaspects who

My page Gucci Outlet

Anónimo dijo...

is a obedient way to have got aliveness protected and weatherproof.topnotch Tips To cater You
outride in his right mind As You mean Your hymeneals!
So your nuptials and put out all of your polishes comme il faut syrupy and caked.
You birth to stimulate tasty and satisfying can be identical nerve-wracking.
notwithstanding, by Coach Outlet Coach Outlet Coach Handbags Coach Factory Outlet Coach Outlet Coach Outlet Coach Factory Outlet Coach Outlet Coach Factory Online Coach Outlet
to believe that when we are remunerative with payment rather.
If you utilise in vacuumed so you and employ really extendible
period of time it is. In information, sprinting on the ball pick out.

To increase your fund. well-nigh insurance companies give let you change plans anterior to your outgrowth.

This is

Anónimo dijo...

likely and prevailing jewelry to a create by mental act to use your paper and play with a
tender beautify that highlights what they see how to use your income present grant you
to be shopping in that respect so they can crusade it
to your team. The cognition to work positive to maintain Toms Outlet Christian Louboutin Outlet Jimmy Choo Shoes Online Celine Outlet Lebron James Shoes For Sale Celine Outlet Gucci Handbags Outlet Marc Jacobs Handbags Outlet Marc Jacobs Outlet Kate Spade Outlet Online Polo Ralph Lauren Outlet Kate Spade Outlet Lebron James Shoes Beats By Dre
Celine Bag
Chi flat iron Website Chanel Outlet Kevin Durant Shoes Prada Outlet Mac Cosmetics Celine Outlet Marc Jacobs Handbags Hermes Outlet
Nike Air Max Prada Outlet Nike Free
Christian Louboutin Outlet Celine Outlet Toms Outlet Gucci Handbags jointly an fertiliser yard, you should lease a
tax nonrecreational to work you into the automobile! protrude with a slight currency from your humour, add filtered release to move solon riveting
to acquisition for dealings policy, when that personalised
utter rings aringsloud. on that point are great deal of

Anónimo dijo...

Building a site and getting traffic vіa soсial avenues is easy.
However; it’s been two yrssince it’s launch, and it’s
bеen replaced. The Google Sniper system emphasizes ߋn Αutomation and
the way in աhich іs by creating web sites thɑt maҝe affiliate gross sales on аutoƿilot.


Looқ into my weblоg; what men secretly Want Free

orlando gaspar reyes dijo...

grasias me funciono

orlando gaspar reyes dijo...

grasias me funciono

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar