Recursiv procedure ?

function find(input : TIntArr) : TIntArr;

var
  dim, i, j, maxix, ix : integer;
  res, seqlen, next : TIntArr;

begin
  dim := high(input) - low(input) + 1;
  SetLength(seqlen, dim);
  SetLength(next, dim);
  maxix := dim - 1;
  for i := dim - 1 downto 0 do begin
    seqlen[i] := 1;
    next[i] := -1;
    for j := i + 1 to dim - 1 do begin
      if input[low(input) + j] > input[low(input) + i] then begin
        if 1 + seqlen[j] > seqlen[i] then begin
          seqlen[i] := 1 + seqlen[j];
          next[i] := j;
        end;
      end;
    end;
    if seqlen[i] > seqlen[maxix] then maxix := i;
  end;
  SetLength(res, seqlen[maxix]);
  ix := maxix;
  for i := 0 to seqlen[maxix] - 1 do begin
    res[i] := input[low(input) + ix];
    ix := next[ix];
  end;
  find := res;
end;

Den er meget tydelig O(n*n), hvilket selvfølgelig ikke er godt, men den laver meget
lidt i det indre loop, så den er alligevel rimelig hurtig.

Jeg lavede det i Delphi fordi din kode var i Delphi.

Algoritmen kan relativt nemt konverteres til C++/Java/C#/whatever.

Mit bud på en algoritme (godt nok skrevet i C#)

namespace e804159
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] inData = { 16, 6, 3, 4, 5, 21, 22, 7, 9, 10, 11, 12, 13, 14, 15 };

            int[] result = FindLargestSeq(inData);
            for (int result_idx = 0; result_idx < result.Length; result_idx++)
            {
                Console.Write(" " + result[result_idx]);
            }
            Console.WriteLine();
        }

        private static int[] FindLargestSeq(int[] inData)
        {
            for (int numbersToRemove = 0; numbersToRemove < inData.Length; numbersToRemove++)
            {
                Combination indicesToRemove = new Combination(inData.Length, numbersToRemove);

                while (indicesToRemove != null)
                {
                    if (IsSequence(inData, indicesToRemove.data))
                        return Sequence(inData, indicesToRemove.data);

                    indicesToRemove = indicesToRemove.Successor();
                }
            }

            return null;
        }

        private static bool IsSequence(int[] inData, int[] indicesToRemove)
        {
            int indicesToRemove_idx = 0;
            bool firstIndex = true;
            int currMax = -1;

            for (int inData_idx = 0; inData_idx < inData.Length; inData_idx++)
            {
                // Er det et af de indices som skal springes over?
                if (indicesToRemove_idx < indicesToRemove.Length &&
                    inData_idx == indicesToRemove[indicesToRemove_idx])
                {
                    indicesToRemove_idx++;
                    continue;
                }

                // Er det første element i inData?
                if (firstIndex)
                {
                    currMax = inData[inData_idx];
                    firstIndex = false;
                    continue;
                }

                // Er det nuværende element større end de forrige?
                if (currMax >= inData[inData_idx])
                    return false;

                currMax = inData[inData_idx];
            }

            return true;
        }

        private static int[] Sequence(int[] inData, int[] indicesToRemove)
        {
            int length = inData.Length - indicesToRemove.Length;
            int[] result = new int[length];
            int result_idx = 0;

            int indicesToRemove_idx = 0;

            for (int inData_idx = 0; inData_idx < inData.Length; inData_idx++)
            {
                if (indicesToRemove_idx < indicesToRemove.Length &&
                    inData_idx == indicesToRemove[indicesToRemove_idx])
                {
                    indicesToRemove_idx++;
                    continue;
                }

                result[result_idx] = inData[inData_idx];
                result_idx++;
            }

            return result;
        }
    }
}

    public class Combination
    {
        // Koden taget fra http://msdn.microsoft.com/msdnmag/issues/04/07/TestRun/#S2
        // Modifiseret, og store dele af koden helt slettet.

        private int n;
        private int k;

        public int[] data;

        public Combination(int n, int k)
        {
            if (n < 0 || k < 0) // normally require n >= k 
                throw new Exception("Negative parameter in constructor");

            this.n = n;
            this.k = k;

            data = new int[k];
            for (int i = 0; i < k; ++i)
                data[i] = i;
        }

        public Combination Successor()
        {
            if (data.Length == 0 || data[0] == n - k)
                return null;

            Combination ans = new Combination(n, k);

            int i;
            for (i = 0; i < k; ++i)
                ans.data[i] = data[i];

            for (i = k - 1; i > 0 && ans.data[i] == n - k + i; --i) ;

            ++ans.data[i];

            for (int j = i; j < k - 1; ++j)
                ans.data[j + 1] = ans.data[j] + 1;

            return ans;
        }
    }

Hej Arne V  og Nielle

Tusind tak for jeres svar. Jeg skal nu sidde og teste og kigge på virkemåde og tider osv.

Men Nielle: Jeg har godtnok lidt svært ved at læse C syntax. Vil du være flink og opsummere hvad de forskellige funktioner gør med lidt pseudo-kode ? Det vil lette det en del for mig.

Tak endnu engang :)

Mit Delphi er desværre lidt rustent – det er vel lidt over 7 år siden at jeg sidst havde gang i pascal. Og du havde jo ikke angivet at du havde nogen specielle preferencer (men jeg kunne selvfølgelig have gættet som arne_v).

Anyways. Den grundlæggende algoritme er simpel:

Jeg tager udgangspunktet i en klasse som kan lave kombinatorik – det er klassen "Combination". Der findes masser af lignende til Delphi. F.eks. denne fra toppen af Google:

http://www.bsdg.org/2004/11/factorials-combinations-and.shtml

Hvis man initialisere den med f.eks.:

Combination indicesToRemove = new Combination(15, 3);

vil man få samtlige kombinationer hvor at man udvælger 3 forskellige tal i intervallet [0, 15[:

{0, 1, 2}
{0, 1, 3}
{0, 1, 4}
...
{0, 2, 3}
{0, 2, 4}
...
{1, 2, 3}
...
{12, 13, 14}

Den måde jeg bruger Combination-klassen på er at den angiver hvilke indekser vi prøver på at *fjerne* for at få den stigende sekvens. Algoritmen prøver først at fjerne 0 indekser, derefter 1 indeks, derefter 2 indekser, osv.. Algoritmen stopper selvfølgelig lige så snart der er fundet en løsning.

Man kunne selvfølgelig også prøve den anden vej rundt – at lade  Combination-klassen angive hvilke indekser der skulle indgå i den sekvens man leder efter. Faktisk tror jeg – nu hvor jeg sidder og skriver dette – at den resulterende kode bliver en smule mere strømlinet. ;^)

Men altså; algoritmen forsøger at fjerne 0 indekser, derefter 1 indeks, derefter 2 indekser, osv.. Det er denne løkke:

// Prøver at fjerne 0, 1, 2, osv indekser.
// Da vi starter med 0 vil vi ende med den længste sekvens.
for (int numbersToRemove = 0; numbersToRemove < inData.Length; numbersToRemove++)
{
    // Opret en kombination som gennemløber antallet af mulige kombinationer
    // af 'numbersToRemove' tal ud af 'inData.Length' tal.
    // (inData er dit oprindelige array)
    Combination indicesToRemove = new Combination(inData.Length, numbersToRemove);

    // Gennemløb samtlige kombinationer.
    while (indicesToRemove != null)
    {
        // IsSequence() tjekker om vi har en stigende sekvens
        // når vi fjerner tallene svarende til indekserne
        // angivet i indicesToRemove. Hvis det er en sekvens,
        // danner Sequence() sekvensen og returnere den. Dette bryder
        // while-løkken og returnere til det kaldende program.
        if (IsSequence(inData, indicesToRemove.data))
            return Sequence(inData, indicesToRemove.data);

        // Næste kombination.
        indicesToRemove = indicesToRemove.Successor();
    }
}

Funktionen:

IsSequence(int[] inData, int[] indicesToRemove)

undersøger om der opnås en sekvens ved at fjerne indicesToRemove fra inData. Dette gøres uden at der oprettes nye array og tal kopieres fra en position til en anden. Dette er nemlig noget som koster performance.

private static bool IsSequence(int[] inData, int[] indicesToRemove)
{
    // Index som løber igennem indicesToRemove arrayet
    int indicesToRemove_idx = 0;

    // Flag så vi kan behandle første element specielt.
    bool firstIndex = true;

    // Bruges til at holde styr på maks efterhånden
    // som vi løber igennem inData arrayet.
    // Det er faktisk ligegyldigt hvad currMax sættes til
    // her - det er udelukkende for at koden kan kompile.
    int currMax = -1;

    // Løb igennem alle elementerne i inData arrayet.
    for (int inData_idx = 0; inData_idx < inData.Length; inData_idx++)
    {
        // Er det et af de indices som skal springes over?

        // Hvis vi ikke er løbet ud over enden af indicesToRemove arrayet, OG
        // indekset vi er nået til i inData er et af dem vi skal springe over
        // ifølge indicesToRemove arrayet, så...
        if (indicesToRemove_idx < indicesToRemove.Length &&
            inData_idx == indicesToRemove[indicesToRemove_idx])
        {
            // ...tæl indekset indicesToRemove_idx 1 op sådan at vi
            // efterfølgende peger på det næste indeks der skal overspringes.
            indicesToRemove_idx++;

            // Spring direkte til næste inData_idx.
            continue;
        }

        // Er det første element i inData?

        // Hvis vi er ved første indeks (som ikke skal overspringes).
        if (firstIndex)
        {
            // currMax initialiseres.
            currMax = inData[inData_idx];

            // Flaget nulstilles.
            firstIndex = false;

            // Spring direkte til næste inData_idx.
            continue;
        }

        // Er det nuværende element større end de forrige?
        if (currMax >= inData[inData_idx])
            return false;

        // Opdater værdien af currMax.
        currMax = inData[inData_idx];
    }

    // Løkken gav ikke grund til at returnere med false.
    // Derfor er det en stigende sekvens.
    return true;
}

Funktionen:

private static int[] Sequence(int[] inData, int[] indicesToRemove)

er blot en variation over IsSequence() ovenfor. Da IsSequence() ikke direkte danner det array der vil være resultatet af at fjerne indicesToRemove fra  inData, er det Sequence()'s job.

Håber at det kastede lys over sagen?

Her er algoritmen i den nye version - hvor der arbejdes med hvad der skal inkluders frem for hvad der skal ekskluderes (Combination-klassen er ikke ændret):

namespace e804159b
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] inData = { 16, 6, 3, 4, 5, 21, 22, 7, 9, 10, 11, 12, 13, 14, 15 };

            int[] result = FindLargestSeq(inData);
            for (int result_idx = 0; result_idx < result.Length; result_idx++)
            {
                Console.Write(" " + result[result_idx]);
            }
            Console.WriteLine();
        }

        private static int[] FindLargestSeq(int[] inData)
        {
            for (int numbersToInclude = inData.Length; numbersToInclude > 0; numbersToInclude--)
            {
                Combination indicesToInclude = new Combination(inData.Length, numbersToInclude);

                while (indicesToInclude != null)
                {
                    if (IsSequence(inData, indicesToInclude.data))
                        return Sequence(inData, indicesToInclude.data);

                    indicesToInclude = indicesToInclude.Successor();
                }
            }

            return null;
        }

        private static bool IsSequence(int[] inData, int[] indicesToInclude)
        {
            bool firstIndex = true;
            int currMax = -1;

            for (int indicesToInclude_idx = 0; indicesToInclude_idx < indicesToInclude.Length; indicesToInclude_idx++)
            {
                int inData_idx = indicesToInclude[indicesToInclude_idx];

                if (firstIndex)
                {
                    currMax = inData[inData_idx];
                    firstIndex = false;
                    continue;
                }

                if (currMax >= inData[inData_idx])
                    return false;

                currMax = inData[inData_idx];
            }

            return true;
        }

        private static int[] Sequence(int[] inData, int[] indicesToInclude)
        {
            int[] result = new int[indicesToInclude.Length];
            int result_idx = 0;

            for (int indicesToInclude_idx = 0; indicesToInclude_idx < indicesToInclude.Length; indicesToInclude_idx++)
            {
                int inData_idx = indicesToInclude[indicesToInclude_idx];
                result[result_idx] = inData[inData_idx];

                result_idx++;
            }

            return result;
        }
    }
}

Hej Nielle

Mange mange tak for foklaringen. Nu tror jeg jeg forstår hvad algoritmen gør

Mht til tidskomplexitet så har jeg fundet frem til følgende:
for én kombination kører algoritmen n!/(r!(n-r)!) hvis combinationsklassen altså tager højde for at rækkefølgen er ligemeget (ex (2, 4, 6) er det samme som (4, 2, 6) og (6, 4, 2) osv) Hvis kombinations klassen bare laver permutationer, så bliver det n!/(n-r)!

For samtlige kombinationer (worst case) så vil den køre i summen af n!/(r!(n-r)!) for r=1 -> n (evt kun op til n/2)

Har jeg forstået det korrekt ?

Hej Arne V

Såvidt jeg kan se, så bliver tidsforbruget O(Tn) altså n+(n-1)+(n-2)+(n-3)...1=n(n+1)/2
Som svarer til n*n/2 for stor n. Er det rigtigt ?

I øvrigt Arne V, må jeg godt spørge om det var noget kode du havde liggende, eller skrev du den bare til lejligheden ? :-)

Det er rigtigt.

Jeg skrev faktisk også at den var O(n*n).

(man glemmer normalt konstanten når man angiver big O d.v.s. at n*n/2 og n*n er det samme)

Den blev konstrueret til lejligheden.

http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem

påstår iøvrigt at det kan løses O(n*log(n))

Combinationsklassen giver tallene i sorteret rækkefølge. Ellers ser dit regnestykke ok ud. :^)

Nu spekulere jeg så på hvorfor at du egentlig tænker i O(...)? Dette har kun relevans hvis at du ønsker at arbejde med længere og lægere sekvenser - altså for n->oo.

Hvis du derimod har en fast øvre grænse for n, så er dette ikke nært så relevant. Du kan sagtens have f.eks. en O(n^3) algoritme, som performer langt bedre end en O(n) på arrays af en bestemt øvre længde. Som arne_v skriver så udelader man normalt konstante faktore.

Med en algoritme som involverer antal combinations, så går det galt lang tid før uendelig.

----

Det er rigtigt at for tilpas små n, så kan en algoritme med dårlige big O egenskaber godt
være hurtigst.

Men prøv og konverter mit forslag til C# og mål.

Hej Arne V og Nielle

Jeg siger mange mange tak for jeres hjælp. Denne gang havde jeg virkelig brug for hjælpen. Det at proceduren nu kører hurtigt betyder at jeg har sparet rigtig rigtig meget bøvl, for ellers skulle havde brugt en hel anden og svær metode.

Jeg synes at I begge har fortjent max point for jeres hjælp. Jeg har oprettet et nyt spørgsmål http://www.eksperten.dk/spm/804587 hvor Nielle kan svare og Arne V kan svare her :-)

Og max karma herfra :-)

>>rozh

Hrm, du har vis overset en af Ekspertens regler, nemlig den, der stipulerer, at man maximalt kan uddele 200 point for et spørgsmål, og det betragtes nærmest som en skærpende omstændighed, at der deles over flere (hvilket jo også er den eneste mulighed for at komme over 200 !-)

-- så du bør selv lukke det andet spørgsmål, og så her dele pointene mellem arne_v og nielle ...

-- og jeg er ret overbevist om, at de også er ganske godt tilfreds med den løsning !o]

OK

svar

Jeg springer over på denne her - arne_v's algoritme er helt klart den hurtigste (er målt efter). :^)

Fair nok. Jeg sætter stor pris på jeres hjælp :-)