Onko tässä mitään tolkkua. Yritys on kovaa!!! Tuo StringComparaattori kyllä toimii. Lopetusehtoa en ymmärrä. Pitääkö olla return ja jos niin, kuinka se Treesetillä muodostetaan?
import java.util.*;
public class Rekursio
{
public static boolean rekurKomb(String mjJono)
{
TreeSet tulosJoukko = new TreeSet(new StringComparatori());
if (mjJono.length()==0)
return ???????;
else
{
for (int i=0; i< mjJono.length();i )
{
String tulosJono=mjJono.substring(i,i 1)
rekurKomb(mjJono.substring(0,i) mjJono.substring(i 1));
tulosJoukko.add(tulosJono);
}
}
return tulosJoukko;
}
public static void main(String[] args)
{
System.out.println("Anna viisimerkkinen merkkijono! ");
String smjTodjono = Lue.rivi();
TreeSet tulosStringit = new TreeSet();
tulosStringit= rekurKomb(smjTodjono);
Iterator tamaIt = tulosStringit.iterator();
while(tamaIt.hasNext());
System.out.println(tamaIt.next());
}
}
import java.util.*;
public class Rekursio
{
public static boolean rekurKomb(String mjJono)
{
TreeSet tulosJoukko = new TreeSet(new StringComparatori());
if (mjJono.length()==0)
return ???????;
else
{
for (int i=0; i< mjJono.length();i )
{
String tulosJono=mjJono.substring(i,i 1)
rekurKomb(mjJono.substring(0,i) mjJono.substring(i 1));
tulosJoukko.add(tulosJono);
}
}
return tulosJoukko;
}
public static void main(String[] args)
{
System.out.println("Anna viisimerkkinen merkkijono! ");
String smjTodjono = Lue.rivi();
TreeSet tulosStringit = new TreeSet();
tulosStringit= rekurKomb(smjTodjono);
Iterator tamaIt = tulosStringit.iterator();
while(tamaIt.hasNext());
System.out.println(tamaIt.next());
}
}
Vastaukset 9
Vanhimmat
Tuo palautusehto kannattaa muuttaa i=1.
tässä allaolevassa on se vika, että rekurKomb palauttaa TreeSetin, jonka sisältönä on merkkijonoja. Yritä käsitellä suoraan niitä merkkijonoja, etkä sitä TreeSettiä. Enpä ole koskaan tarvinnut tällaista ratkaisua.
juu jatkakoon...
{
String tulosJono=mjJono.substring(i,i 1)
rekurKomb(mjJono.substring(0,i) mjJono.substring(i 1));
tulosJoukko.add(tulosJono);
}
Tämä on kenties puutteellinen ohjelmanpätkä, mutta muuttaisin seuraavasti:
======================================
import java.util.*;
public class Rekursio
{
public static void main(String[] args) {
String testiMj="abcde";
Set kombinaatiot=new HashSet();
rekurComb(testiMj,kombinaatiot);
}
public static void rekurKomb(String mjJono, Set tulos) {
if(!tulos.contains(mjJono))
tulos.add(mjJono);
if(1
Millainen lopputuloksen pitäisi olla? Jos merkkijono on abc niin ohjelma antaa:
===========================================
abc
bc
c
b
ac
a
ab
===========================================
Eli sellainen kuin ongelmasi ratkaisuksi ymmärsin mutta onko tulos oikea?
abc jonosta pitisi saada;
a, b, c, ab, ac, ba, bc, ca, cb, abc, acb, bad, bca, cab, cba
uusin yritykseni on tässä:
import java.util.*;
public class TaasRekur
{
static TreeSet tulosJoukko = new TreeSet(new StringComparatori());
public static TreeSet rekurKomb(String mjJono)
{
if (mjJono.length()==1)
{
Iterator itLpo = tulosJoukko.iterator();
while (itLpo.hasNext())
{
String viim =(String)itLpo.next() mjJono.substring(mjJono.length()-1);
tulosJoukko.add(viim);
}
}
else
{
for (int i=0; i< mjJono.length();i )
{
Iterator itAlku= tulosJoukko.iterator();
while (itAlku.hasNext())
{
String alku = (String)itAlku.next();
String tulosJono = alku mjJono.substring(i,i 1);
tulosJoukko.add(tulosJono);
rekurKomb(mjJono.substring(0,i) mjJono.substring(i 1));
}
}
}
return tulosJoukko;
}
public static void main(String[] args)
{
String todellinen= "abcde";
TreeSet tulosStringit = new TreeSet();
tulosStringit= rekurKomb(todellinen);
Iterator tamaIt = tulosStringit.iterator();
while(tamaIt.hasNext());
{
System.out.println(tamaIt.next());
}
}
}
Hmmm... En tiedä onko tolkkua, mutta yritys on ainakin hyvää. :). Itse ratkaisisin asian seuraavasti:
--- ESIMERKI ALKAA ---
public class Rekursiivinen
{
public static void rekursiivinen(String alku, String kirjaimet) {
for (int i = 0; i < kirjaimet.length(); i ) {
char kirjain = kirjaimet.charAt(i);
if (kirjaimet.indexOf(kirjain) == i) {
String kombinaatio = alku kirjain;
String uudetKirjaimet = kirjaimet.substring(0, i) kirjaimet.substring(i 1);
System.out.println(kombinaatio);
rekursiivinen(kombinaatio, uudetKirjaimet);
}
}
}
public static void main(String[] args) {
rekursiivinen("", "abc");
}
}
--- ESIMERKKI LOPPUU ---
Eli periaate on se että argumentti nimeltä "kirjaimet" sisältää sen merkkijonon josta ne kombinaatiot muodostetaan ja argumentti nimeltä "alku" sisältää sen aloitus merkki jonon joka liitetään näiden uusien kombinaatioiden eteen. Uusi kombinaatio muodostetaan aina sillä periaatteella että otetaan yksi kirjain "kirjaimet" merkkijonosta ja lisätään se "alku" merkkijonoon. Ehto "if (kirjaimet.indexOf(...))" varmistaa sen että saman kirjaimen kanssa ei muodosteta uutta kombinaatiota useampaan kertaan. Kun uusi kombinaatio on muodostettu niin tämän jälkeen tehdään rekursiivinen kutsu, siten että "alku" argumenttina käytetään uutta kombinaatiota, ja "kirjaimet" argumenttina käytetään vanhaa "kirjaimet" merkkijonoa josta on poistettu se kirjain jonka avulla uusi kombinaatio on muodostettu. "alku" ja "kirjaimet" argumentit sisältävät siis yhdessä koko ajan kaikki alkuperäisen sanan kirjaimet.
Kiitos.Ratkaisusi on upea. Yritän kuitenkin itsepäisesti saada saman tehtyä TreeSetin avulla.
Yritän ratkaista tehtävää niin, että alussa on TreeSetissä tyhjä merkkijono. Sitten lisään vuorotellen jokaisen merkin merkkijonsta tähän tyhjään merkkijonoon. Näin saadut uudet merkkijonot talletan TreeSettiin. Sen jälkeen kutsun rekursiivisesti funtiota, joka tekee saman jokaiselle TreeSetissä olevalle merkkijonolle käyttäen parametrinä vielä käyttämättä olevaa loppuosaa alkuperäisestä merkkijonosta.
Tarkoitukseni on tallentaa jokainen kombinaatio vuorollaan TreeSettiin. Ja kutsua sieltä tallennettuja merkkijonoja, mutta minun pitäisi kusua vain niitä merkkijonoja, jotka on viimeksi talleennettu, eli joiden pituus on suurin.
Metodin pitäisi palauttaa TreeSetti. TreeSetissä on oma comparaattori, joka tulostaa tulosjonot iteroitaessa pituusjärjestyksessä.
Voiko ongelman ratkaista niin?
Juu, kyllä sen varmaan jotenkin niinkin saa tehtyä. Tulee kuitenkin muistaa se että, et saa rinnakkain lisätä TreeSet:iin uutta oliota sekä käsitellä siitä otettua Iterator oliota. Valitettavasti tämä ongelman rekursiivinen lähestymistapa johtaa helposti tällaiseen rinnakkaiseen käsittelyyn, jolloin ohjelma voi heittää "ConcurrentModificationException" poikkeutuksen. Tästä fail-fast ominaisuudesta on puhuttu mm:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/TreeSet.html
Jos olet saanut käännettyä tuon sinun tuossa yhdessä viestissä olevan koodin, niin voi olla että olet jo törmännytkin kyseiseen poikkeukseen.
Itse en näe noiden "jotakinSet" luokkien käyttöä kovin suotavana tämän ongelman ratkaisussa. Yleensä tällaisissa kombinaatio ongelmissa rekursiivisella lähestymistavalla pyritään pääsemään siihen, ettei kaikkia turhia/samoja kombinaatiota käytäisi läpi. Näiden "jotakinSet" luokkien käyttö ongelmaa ratkottaessa johtaa helposti siihen että tehdään ratkaisu jossa kaikki turhat/samat kombinaatiot käydään läpi ja annetaan vain "jotakinSet" luokan olion hoitaa se ettei turha kombinaatio tallennu "toistamiseen". Toki näitä "jotakinSet" luokkia voi sitten käyttää juuri siihen tiedon loppu tallennukseen. Tässä ongelmassa voisi olla hyvä esimerkiksi miettiä sitä, miten ohjelma käyttäytyy jos merkkijonona olisi vaikka "aaaaaaaaaaaaaaaaaa" tai "aaaaaaabaaaaaaa", eli selviääkö ohjelma kyseisistä jonoista kohtuuajassa vai kestääkö sillä useampi sekunti.
Kun katson tuota sinun aloitus viestin koodiasia, niin olet aika hyvin pääsyt siinä juonesta kiinni. Välität koodissasi rekursiiviselle kutsulle aina eteenpäin ne kirjaimet joilla uudet kombinaatiot muodostetaan (kutsut sitä näköjään "mjJono":ksi joka ehkä vähän hämää). Lisäksi teet rekursiivisen kutsun aina merkkien määrän verran, mikä sekin on aivan oikein. Se miten muodostat uuden kombinaation käyttämällä sanan loppu osaa, jne. on vähän hämäävää. Koodisi perusteella näyttäisi siltä että yrität lähestyä ongelmaa siltä kannalta, että yrität muodostaa n:stä alkiosta kaikki eri kombinaatiot ja senkin tehdä käänteisesti, jne... Jos en olisi tuohon esimerkki koodiini laittanut sitä "indexOf" ehtoa niin silloin ohjelma olisi tulostanut n:n alkion "kaikki" kombinaatiot, josta sitten jollakin "jotakinSet" luokan oliolla avulla olisi saanut myös oikean tuloksen... En tiedä helpottaisiko se ongelman lähestymistä jos yrittäisit lähestyä ongelmaa niin kuin todennäköisesti tekisit sen paperilla, eli ensin muodostaisit yhden kirjaimen "kombinaation" ja tämän jälkeen kahden kirjaimen "kombinaation" jossa alku osana olisi se juuri muodostamasi kombinaatio ja lisä kirjaimena joku jäljellä olevista kirjaimista, jne. (Se for silmukka on juuri sitä varten että se takaa sen että jokainen kirjain toimii vuoron perää "aloitus" kirjaimena...).
Se yksinkertaisuus taisi olla minun korvie...
Tällaista minä tavoittelin, vaan en osannut. Tuo oma String comparatori pistää jonot pituusjärjestykseen. Pahin virheeni luultavasti oli yrittää käyttää sitä loppuosaa sieltä TreeSetistä käsin. Tuon if ehdon ilmeisesti voisi poistaa tai merkitä if(true), mutta silloin tulisi turhia kierroksia. Ei tuo TreeSetti kuitenkaan ottaisi vastaan niitä toistoja. Luulisin? Kiitokset avusta, kyllä tässä vielä piisaa pähkäilyä. sijoittelin sinne koodiin muutamia System.out.printlnniä muuttujille ja ajelin debuggerilla. aloittelevan koodaajan elämnä on kovaa...
import java.util.*;
public class Yksi
{
public static TreeSet tulosJoukko= new TreeSet();
public static TreeSet rekursiivinen(String alku, String kirjaimet)
{
for (int i = 0; i < kirjaimet.length(); i )
{
char kirjain = kirjaimet.charAt(i);
if (kirjaimet.indexOf(kirjain) == i)
{
String kombinaatio = alku kirjain;
String uudetKirjaimet = kirjaimet.substring(0, i) kirjaimet.substring(i 1);
tulosJoukko.add(kombinaatio);
rekursiivinen(kombinaatio, uudetKirjaimet);
}
}
return tulosJoukko;
}
public static void main(String[] args)
{
TreeSet lopullinen= new TreeSet(new StringComparatori());
lopullinen = rekursiivinen("","abc");
Iterator tamaIt = lopullinen.iterator();
while (tamaIt.hasNext())
System.out.println(tamaIt.next());
}
}
Hienoa! Juu, sen "if" ehdon voisi todellakin poistaa mainitsemastasi syystä, eli siitä että TreeSet takaa sen ettei sama jono tallennu kahteen kertaan. Siitä "if" ehdon pois jättämisestä tulee tosiaan vain niitä ylimääräisiä kierroksia, kuten mainitsit, koska silloin käydään kaikki n:n alkion kombinaatiot läpi.
Jos ongelma olisi puhtaasti matemaattinen eikä tarvitsisi välittää tuosta esitys tavasta, niin käyttäisin silloin TreeSet:n sijaista vaikka normaalia Vector:ia, tms. Sillä tämä TreeSet:n suorittama vertailu operaatioiden määrä "add" metodin yhteydessä, ei yleensä ole mikään vähäinen. Mutta tämä on sitten jo sitä optimointia... :)
Noista koodin sijoitelluista "println" käskyistä on todellakin usein paljon hyötyä. Itse käytän niitä aina silloin kun joku asia ei mene mielestäni siten kuin pitäisi. Debuggereita en ole vielä oppinut käyttämään (muuta kuin DOS:n debug ohjelmaa) :-(.
Yleensä nämä tällaiset matemaattiset ongelmat saa aina suht pienillä ja yksinkertaisilla koodin pätkillä ratkaistua...