Új hozzászólás Aktív témák

• #9468 joysefke veterán pmonitor #9466

  Új Válasz 2021-02-13 20:44:57 #9468

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  joysefke

  veterán

  LOGOUT blog

  válasz pmonitor #9466 üzenetére

  Átírva C#-ba és használható formában
  A kezdeti 1x tömb-klónozáson kívül (hogy ne legyen elrontva a bemeneti tömb) teljesen allokációmentes.
  A char[] State tárolja az aktuális állapotot, a bool Next() pedig lépteti az és visszajelez a sikerről. Ha a char[] State állapotot nem csak olvasni akarod akkor értelemszerűen ki kell menteni róla egy másolatot.

  A char[] State köré lehetne még valami readonly wrappert rakni, de azt nem tudom hogy viselkedne.

  char[] megy bele ctor bemeneti paraméterként

  És ezen még lehetne gyorsítani.

  using System;
namespace Permutator
{
    class Program
    {
        static void Main(string[] args)
        {
            int i = 0;
            var p = new Permutator("abcdananana".ToCharArray());
            do
            {
                i++;
                Console.WriteLine(new string(p.State));
            }
            while (p.Next());
            Console.WriteLine($"Nr of results: {i}");
        }
    }
    public class Permutator
    {
        public char[] State { get; }
        int _size;
        bool isFinished = false;
        public Permutator(char[] symbols)
        {
            if (symbols?.Length > 0)
            {
                _size = symbols.Length;
                State = (char[])symbols.Clone();
                Array.Sort(State);
            }
            else
                throw new ArgumentException("input must be non-empty");
        }
        public bool Next()
        {
            // if we have already finished we indicate failure on getting next element
            // else we try to advance the state and propagate success of advancing state
            if (isFinished)
                return false;

            isFinished  = !AdvanceState();
            return !isFinished;
        }
        bool AdvanceState()
        {
            // Find the rightmost character 
            // which is smaller than its next 
            // character. Let us call it 'first 
            // char' 
            int i;
            for (i = _size - 2; i >= 0; --i)
                if (State[i] < State[i + 1])
                    break;
            // If there is no such character, all 
            // are sorted in decreasing order, 
            // means we just printed the last 
            // permutation and we are done. 
            if (i == -1)
                return false;
            // Find the ceil of 'first char' 
            // in right of first character. 
            // Ceil of a character is the 
            // smallest character greater 
            // than it 
            int ceilIndex = findCeil(State, State[i], i + 1, _size - 1);
            char tmp = State[i];
            State[i] = State[ceilIndex];
            State[ceilIndex] = tmp;
            Array.Sort(State, i + 1, _size - i - 1);
            return true;
        }
        // This function finds the index of the 
        // smallest character which is greater 
        // than 'first' and is present in str[l..h] 
        int findCeil(char[] str, char first, int l, int h)
        {
            // initialize index of ceiling element 
            int ceilIndex = l;
            // Now iterate through rest of the 
            // elements and find the smallest 
            // character greater than 'first' 
            for (int i = l + 1; i <= h; i++)
                if (str[i] > first && str[i] < str[ceilIndex])
                    ceilIndex = i;
            return ceilIndex;
        }
    }
}

  [ Szerkesztve ]

Új hozzászólás Aktív témák