dotNETportal.cz

Ahoj, můžete mi prosím poradit, nebo teoreticky navést k tomu, jak napsal algoritmus (C#), který bude umět vytvořit seznam všech kombinací daných znaků?

Například, vstup: abcdef

Výstup:

a

aa

ab

ac

ad

...

aaa

aab

aac

...

eeeee

eeeef

eeeeg

až po

ffffff

Mělo by to pracovat nezávisle na počtu znaků na vstupu. Jde mi o všeobecný algoritmus. Proto bez různých vychytavek .NET jako třeba Linq, atd.

Děkuji :-)

Pokud by šlo pouze o vypsání možných kombinací konkrétního příkladu :

        Dim al As New ArrayList
        Dim foo As String = "abcdef"
        For Each c1 As Char In foo
            Debug.WriteLine(c1)
            al.Add(c1)
            For Each c2 As Char In foo
                Debug.WriteLine(String.Join("", c1, c2))
                al.Add(String.Join("", c1, c2))
                For Each c3 As Char In foo
                    Debug.WriteLine(String.Join("", c1, c2, c3))
                    al.Add(String.Join("", c1, c2, c3))
                    For Each c4 As Char In foo
                        Debug.WriteLine(String.Join("", c1, c2, c3, c4))
                        al.Add(String.Join("", c1, c2, c3, c4))
                        For Each c5 As Char In foo
                            Debug.WriteLine(String.Join("", c1, c2, c3, c4, c5))
                            al.Add(String.Join("", c1, c2, c3, c4, c5))
                            For Each c6 As Char In foo
                                Debug.WriteLine(String.Join("", c1, c2, c3, c4, c5, c6))
                                al.Add(String.Join("", c1, c2, c3, c4, c5, c6))
                            Next
                        Next
                    Next
                Next
            Next
        Next

Bohužel je to ve vb.net, ale převod nebude nijak složitý, 6x vnořené smyčky.

Aby bylo nezávislé na počtu znaků, tak by šlo použít rekurzivní sama sebe volající funkci s jednou smyčkou v závislosti na délce retězce resp. počtu znaků, ovšem netuším, není-li v rozporu se zadáním ani jakým způsobem má být výsledek vrácen. Snad ještě někdo poradí mnohem lépe nebo zkuste pohledat nějaký generátor kombinací pomocí google pro inspiraci.

...

Pro výpočet celkového počtu možností, nazývají to variace s opakováním, kde záleží na pořadí a prvky se opakují. Pro konkrétní příklad jsou to šestice znaků a pětice a čtveřice a ... až po jednotlivé znaky.

Lze ověřit dle počtu prvků arraylistu a kupodivu to souhlasí.

...

Tedy dle zadání :

6 ^ 6 + 6 ^ 5 + 6 ^ 4 + 6 ^ 3 + 6 ^ 2 + 6 ^ 1 = 46656 + 7776 + 1296 + 216 + 36 + 6 = 55986

...

Operátor ^ funguje ve VB.NET jako mocnina, v C# dělá bitovou operaci XOR.

V C# je pro umocnění je funkce Math.Pow.

Pokus naplnit list všech kombinací daných znaků 'abcdef' od jednotlivých znaků až po kombinace stejné délky jako vstupní řetězec (resp. pracovat dle počtu znaků na vstupu) :

    Dim combinations As New List(Of String)
    GetCombinations("abcdef", combinations)

Vrací 55986 kombinací daných znaků od 'a' po 'ffffff'.

VB.NET :

    Private Sub GetCombinations(ByVal characters As String, _
            ByRef cbls As List(Of String), Optional ByVal ch As String = "")
        For Each c As Char In characters
            cbls.Add(String.Join("", ch, c))
            If characters.Length > cbls(cbls.Count - 1).Length Then
                GetCombinations(characters, cbls, cbls(cbls.Count - 1))
            End If
        Next
    End Sub

C# by code converter :

private void GetCombinations(string characters, ref List<string> cbls, string ch = "")
{
    foreach (char c in characters)
    {
        cbls.Add(string.Join("", ch, c));
        if (characters.Length > cbls(cbls.Count - 1).Length)
        {
            GetCombinations(characters, ref cbls, cbls(cbls.Count - 1));
        }
    }
}

I support you and vote

A very useful piece of code, thank you for sharing

https://www.bestvipblog.com