[delphi] Maken van mogelijike combinaties - Softwareontwikkeling

vrijdag 19 juli 2002 13:26

Acties:

Topicstarter

Ik heb een tekst file met getallen op iedere regel. Nu wil ik deze getallen op alle mogelijke manieren combineren en in een tekst file zetten. Heeft iemand een suggestie hoe ik die oplos.

input:
1
2
3

output:
1
2
3
12
13
21
23
31
32
123
132
213
231
312
321

vrijdag 19 juli 2002 13:37

Acties:

Confusion

Fallen from grace

Met recursie

Wie trösten wir uns, die Mörder aller Mörder?

vrijdag 19 juli 2002 13:42

Acties:

Aetje

Troubleshooting met HAMERRR

1 bepaal aantal regels

Voor elke regel:
- Schrijf elke regel
- Schrijf elke regel + Schrijf elke regel
- Schrijf elke regel + schrijf elke regel + schijf elke regel
ect.

En schijf 't zelf maar om naar code.

[Editje] Kan ook best iteratief hoor...

Forget your fears...
...and want to know more...

vrijdag 19 juli 2002 17:35

Acties:

TheLunatic

Ouwe boxen.

De input getallen zijn : 1 tot x

De output getallen zijn : 1 tot y
[code]var i, j, x, y: Integer;

begin

for i:=1 to x do
for j:=1 to y do
WriteLn(Tekstfile,IntToStr(i)+' '+IntToStr(j));

end;[/code]
Niet recursief, wel makkelijk

Fuck ik kan niet lezen

Mother, will they like this song?

vrijdag 19 juli 2002 17:48

Acties:

Confusion

Fallen from grace

Aetje schreef:
Voor elke regel:
- Schrijf elke regel
- Schrijf elke regel + Schrijf elke regel
- Schrijf elke regel + schrijf elke regel + schijf elke regel, etc.
[..]
[Editje] Kan ook best iteratief hoor...

Volgens mij kan het niet iteratief; je weet vantevoren namelijk niet hoeveel 'levels' diep je moet gaan en als je dat wel weet moet je voor elk level een for-lus nesten; niet bepaald netjes of herbruikbaar.

Dit zijn trouwens alle permutaties (wat de topicstarter bedoelde), niet combinaties (wat de topicstarter vroeg).

Wie trösten wir uns, die Mörder aller Mörder?

vrijdag 19 juli 2002 19:43

Acties:

LordLarry

Aut disce aut discede

Niets hoeft recursief. Alles wat recursief kan kan ook iteratief. Recursief maakt het soms alleen veel beter leesbaar en veel logischer.

We adore chaos because we like to restore order - M.C. Escher

vrijdag 19 juli 2002 20:02

Acties:

Confusion

Fallen from grace

LordLarry schreef:
Niets hoeft recursief. Alles wat recursief kan kan ook iteratief. Recursief maakt het soms alleen veel beter leesbaar en veel logischer.

Ah inderdaad, ik zie nu hoe het recursief kan. Elegant is anders though.

[knip iteratioeve code; sloeg nergens op... recursief is toch echt makkelijker hier ;)]

Wie trösten wir uns, die Mörder aller Mörder?

vrijdag 19 juli 2002 22:45

Acties:

riezebosch

als ik het goed lees, mogen er dus niet twee keer hetzelfde getal in een regel voorkomen (zoals 11)?

Canon EOS 400D + 18-55mm F3.5-5.6 + 50mm F1.8 II + 24-105 F4L + 430EX Speedlite + Crumpler Pretty Boy Back Pack

vrijdag 19 juli 2002 22:53

Acties:

Juicy

Is dit huiswerk ?!

-

vrijdag 19 juli 2002 23:26

Acties:

creative8500

freedom.

Op vrijdag 19 juli 2002 22:53 schreef Juicy het volgende:
Is dit huiswerk ?!

Ik vraag het me af, gezien zijn profiel: "Studierichting: Chemical Engineering"

zaterdag 20 juli 2002 12:41

Acties:

Aetje

Troubleshooting met HAMERRR

Op vrijdag 19 juli 2002 17:48 schreef Fused het volgende:

[..]

Volgens mij kan het niet iteratief; je weet vantevoren namelijk niet hoeveel 'levels' diep je moet gaan en als je dat wel weet moet je voor elk level een for-lus nesten; niet bepaald netjes of herbruikbaar.

Dit zijn trouwens alle permutaties (wat de topicstarter bedoelde), niet combinaties (wat de topicstarter vroeg).

Kan wel iteratief, door de eigenschappen van de gevraagde reeks (is truukje). Recursief is hier idd beter, maar het iteratieve vbtje. PS werk hier niet met FOR lussen, dat gaat geheid fout. While is beter.

code:

procedure TForm1.Button1Click(Sender: TObject);
var i,j:integer;
    IntArr:array of Integer;
    tmpstr:String;
    infile:textfile;

begin
  i:=0;
  j:=0;
  reset(infile);

  while NOT eof(infile) do
  begin
    Readln(infile,tmpstr);
    IntArr[j]:=StrToInt(tmpstr);
    i:= i+1;
  end; //i=aantal regels =&gt; aantal getallen.
end;

<< Rest volgt. Ik moet nu weg >>

Forget your fears...
...and want to know more...

zondag 21 juli 2002 01:23

Acties:

crisp

Devver

Pixelated

ff in javascript

:

code:

&lt;html&gt;
&lt;head&gt;
&lt;title&gt;Permutaties&lt;/title&gt;
&lt;script type=&quot;text/javascript&quot;&gt;

var resultHTML;

function calculate() {

  var nums = document.getElementById('nums').value;
  var numA = new Array();
  resultHTML = '';

  for (var i = 0; i &lt; nums.length; i++) { numA[i] = nums.substring(i, i+1); }

  for (var i = 0; i &lt; numA.length; i++) {

    permut(numA, i, '');

  }

  document.getElementById('results').innerHTML = resultHTML;

}

function permut(A, num, org) {

  for (var i = 0; i &lt; A.length; i++) {

    if (num == 0) {
    resultHTML += org+A[i]+'&lt;br /&gt;';
    } else {
    var B = new Array();
    for (var t = 0; t &lt; A.length; t++) {
      if (t != i) B[B.length] = A[t];
    }
    var neworg = org + A[i];
    permut(B, num-1, neworg);
    }

  }

}

&lt;/script&gt;
&lt;/head&gt;
&lt;body&gt;
&lt;input type=&quot;text&quot; id=&quot;nums&quot;&gt;&lt;/input&gt; &lt;input type=&quot;button&quot; value=&quot;calculate&quot; onClick=&quot;calculate()&quot;&gt;&lt;/input&gt;&lt;br /&gt;
&lt;div id=&quot;results&quot;&gt;&lt;/div&gt;
&lt;/body&gt;
&lt;/html&gt;

Intentionally left blank

dinsdag 23 juli 2002 08:36

Acties:

EvdB

Topicstarter

Is dit huiswerk!?
[..]

Ik vraag het me af, gezien zijn profiel: "Studierichting: Chemical Engineering"

Ik heb de studierichting Chemical Engineering gevolgd en ben nu werkzaam als process engineer.
Dit probleem is puur uit nieuwsgierigheid. De input range is variabel wat het probleem lastig maakt.

dinsdag 23 juli 2002 08:41

Acties:

crisp

Devver

Pixelated

Op dinsdag 23 juli 2002 08:36 schreef EvdB het volgende:

[..]

Ik heb de studierichting Chemical Engineering gevolgd en ben nu werkzaam als process engineer.
Dit probleem is puur uit nieuwsgierigheid. De input range is variabel wat het probleem lastig maakt.

Als je de code boven je eens probeert te doorgronden zal je zien dat het echt niet zo lastig is...

Intentionally left blank

dinsdag 23 juli 2002 08:43

Acties:

EvdB

Topicstarter

Ik heb geen verstand van javascript, maar ik zal het eens proberen.

dinsdag 23 juli 2002 23:04

Acties:

crisp

Devver

Pixelated

Ik zal een poging doen de code uit te leggen:
Dit is dus in zijn totaliteit een HTML pagina die je zo in notepad kan plakken en als .html kan opslaan om vervolgens in je browser te openen.
Er zit een inputveld in waar je de combinatie (bijvoorbeeld 123) in kan opgeven; als je op de knop drukt komen daaronder de permutaties van die combinatie te staan.

De functie calculate() doet niets anders dan de ingevoerde combinatie in een array zetten, die array heet dus numA en bij invoer van 123 wordt die als volgt gevuld:

code:

1
2
3

numA[0] = 1;
numA[1] = 2;
numA[2] = 3;

Vervolgens wordt er een loopje aangeroepen om eerst alle permutaties van 1 lang te vinden; vervolgens die van 2 lang, en als laatste die van 3 lang. De functie permut() wordt dan aangeroepen met 3 parameters:
1) de numA array
2) de lengte-1
3) een (nu nog) lege string

Hier draait het dus om:

code:

function permut(A, num, org) {

  for (var i = 0; i &lt; A.length; i++) {

    if (num == 0) {
    resultHTML += org+A[i]+'&lt;br /&gt;';
    } else {
    var B = new Array();
    for (var t = 0; t &lt; A.length; t++) {
      if (t != i) B[B.length] = A[t];
    }
    var neworg = org + A[i];
    permut(B, num-1, neworg);
    }

  }

}

Dit is dus een recursieve functie omdat hij zichzelf weer aan kan roepen.
Stel dat ik alle permutaties van 2 lang wil vinden met de reeks 123; de originele aanroep wordt dan:

code:

1	permut({1,2,3},1,'');

De loop in de permut() functie pakt uit het eerste argument (de array; binnen de functie genaamd A) het eerste element (1).
Het tweede argument (num) is niet gelijk aan 0, dus komen we in de else constructie.
Hier wordt een 2e array gevuld (genaamd

met alle elementen uit A behalve het 1e element. B wordt dus {2,3}.
Verder vullen we de 3e parameter (genaamd org; en die nu nog leeg is) aan met het 1e element uit A (wat dus niet in B voorkomt): org wordt dus '1'

Nu komen we bij de recursie, want we roepen vanuit de permut() functie weer de permut() functie aan, maar nu met B, num-1 en org als variabelen:

code:

1	permut({2,3},0,'1');

weer komen we in de loop terecht die allereerst wederom het 1e element uit de 1e parameter pakt: 2
Nu is num (de 2e parameter) wel 0, dus komen we in het 1e gedeelte van de if-else constructie terecht.
Deze vult de laatste parameter (org, die dus '1' is) aan met het huidige element uit de 1e parameter (2). Dit levert dus '12' op wat een geldige permutatie van 2 lang is, dus bewaren we die in een globale string (resultHTML) gevolgd door een enter (<BR /> in HTML) om later naar het scherm te kunnen schrijven.

Nu komen we weer in de for loop terecht die het 2e element uit de 1e parameter neemt (3).
num is nog steeds 0, dus wordt de combinatie '13' ook weggeschreven als geldig resultaat.

Alle elementen uit de 1e parameter ({2,3}) zijn nu verwerkt, dus keren we terug naar de originele aanroep van de functie.

Hier is de 1e parameter nog steeds {1,2,3}; num is nog steeds 1 en org is nog steeds leeg; echter komen we weer terug in de for-loop die nu het 2e element uit de 1e parameter pakt (2).
Omdat num 1 is komen we weer in de else constructie waar de array B ditmaal gevuld wordt met {1,3}

Weer roepen we recursief de permut() functie aan ditmaal als:

code:

1	permut({1,3},0,'2');

en het verhaal hierboven herhaald zich weer wat de permutaties '21' en '23' oplevert

Als het laatste element uit de oorspronkelijke 1e parameter ook zo verwerkt wordt krijgen we nog '31' en '32' als geldige permutaties; nu zijn ook alle elementen uit de array van de 1e aanroep verwerkt en zijn alle permutaties van 2 lang gevonden.

Een lange uitleg voor een kort stukje code, maar recursieve functies laten zichzelf meestal erg lastig lezen. Daarentegen zijn ze wel bijzonder krachtig, maar je moet oppassen voor infinite loops....

Intentionally left blank

donderdag 25 juli 2002 08:35

Acties:

EvdB

Topicstarter

Ontzettend bedankt Crisp! Mag gezegd worden als een medetweaker zoveel tijd en geduld heeft om een nieuwe newbie tweakers te helpen.
Nu ik weet dat het permutaties en combinaties zijn heb ik ook zoiets gevonden op:

[url="http://www.delphiforfun.org/Programs/Permutes_2.htm"]http://www.delphiforfun.org/Programs/Permutes_2.htm[/url]

misschien iets waar andere wat aan hebben.