Permutacje znaków

[axlinux]

Witam

Muszę napisać w Javie funkcję, która zwróci wszystkie permutacje wprowadzonych znaków.

np. wprowadzam znaki: abcd a funkcja w tablicy zwraca np.

abcd, abdc, acdb, cdba itp...

Trochę się już z tym męczę

[ultr]

Proponuję funkcję rekurencyjną.

Javy nie lubię i dawno nie używałem, więc napiszę w Qt. Logika jest jedna.

Kod: [Zaznacz]

#include < QString>
#include < QStringList>

void perm( QStringList *list, QString chars, QString begin="" )
{
	if( chars.length() <= 1 )
	{
		list->push_back( begin+chars );
		printf( "%s\\n", (begin+chars).toUtf8().data() ); //
		return;
	}
	for( int k=0; k < chars.length(); k++ )
	{
		QString chars2 = chars;
		chars2.remove( k, 1 );
		perm( list, chars2, begin+chars.at(k) );
	}
}

int main()
{
	QStringList list;
	QString chars = "abcd";
	perm( &list, chars );
	// ...
}

[ZipoKing]

Kiedyś napisałem swojemu znajomemu coś podobnego w C i po paru przeróbkach + przetłumaczeniu na Jave powinno działać : http://zipoking.wordpress.com/2008/01/27/kombinator/

[axlinux]

Dzięki wielkie za posty i za kod.

Sprawdziłem najpierw kod od ULTR-a. Przepisanie tego do Javy oczywiście nie sprawiło kłopotu, jednak wg mnie zamiast:

if( chars.length() <= 1 )  powinno być  if( chars.length() == 0 ) bo generuje po dwa takie same permutacje

Kod: [Zaznacz]

public static void main(String[] args)
    {
       ArrayList lista = new ArrayList();
       perm(lista, "abcd", "");

    }

    public static void perm(ArrayList lista, String znaki, String begin)
    {
        if(znaki.length() == 0)
        {
            lista.add(begin + znaki);
            System.out.println(begin + znaki);
        }

        for(int k=0 ; k < znaki.length() ; k++)
        {
            String znaki2 = znaki.substring(0, k) + znaki.substring(k+1, znaki.length());
            perm(lista, znaki2, begin+znaki.charAt(k));
        }
    }

[ultr]

Dokładnie to powinno być if( chars.length() == 1 ).

Wpisując zero też działa, ale wykonuje jedno niepotrzebne wywołanie funkcji z begin równym całej permutacji i chars="". Kwestia wyboru.

Jeśli używasz 0, to logicznie byłoby napisać dalej:
if(znaki.length() == 0)
{
  lista.add(begin);
  System.out.println(begin);
  return;
}


EDIT: Nie zauważyłem błędu w poprzednim kodzie. W if-ie powinien być return. To dlatego były powtórzone wyniki.