Solved

Logic Problem

Posted on 2000-05-18
22
143 Views
Last Modified: 2010-04-04
hi ... if i've got a set of numbers say "123", how the shortest formula to
resulting the permutation of them to be : "123","132","213","231","312","321"? the result could be flexible depends on the length of numbers, right?


0
Comment
Question by:powerfool
  • 7
  • 6
  • 5
  • +4
22 Comments
 
LVL 9

Accepted Solution

by:
ITugay earned 50 total points
ID: 2820679
Hi,
the working sample is bellow:


type
  TForm1 = class(TForm)
    LB: TListBox;
    SpeedButton1: TSpeedButton;
    procedure SpeedButton1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

function GenVariant(aBase,aWork : string) : string;
var I : integer;
begin
  if aWork = '' then Form1.LB.Items.Add(aBase) else
  for I:=1 to length(aWork) do
  begin
    result:=aWork;
    delete(result,I,1);
    GenVariant(aBase+aWork[I],result);
  end;
end;

procedure TForm1.SpeedButton1Click(Sender: TObject);
begin
  GenVariant('','123');
end;


-----
Igor.
0
 

Expert Comment

by:Grayl1
ID: 2821531
Hi!

Do you want just one random combination or all of them?
0
 
LVL 2

Expert Comment

by:mullet_attack
ID: 2821685
Hey Igor, nice code :-)
0
Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

 
LVL 1

Expert Comment

by:sageryd
ID: 2825012
Nice code Igor, but how does it really work?
0
 
LVL 1

Expert Comment

by:sageryd
ID: 2825015
Just a tip:

if n is the number of characters in the input string, then n! is the number of possible combinations.


--johan
0
 
LVL 1

Author Comment

by:powerfool
ID: 2825213
that's a good logic, is there anyone could give other alternative? I will give my point in few next days ok ...
thanks to igor.
0
 
LVL 9

Expert Comment

by:ITugay
ID: 2828641
Hi all,
I will try to explain my logic. It's very easy;)

To make all combination from the string you need to iterate through all characters in string.  
.....
 for I:=1 to length(aWork) do
.....
then you need to extract (delete) current character and iterate through remain of the string.
.....
    result:=aWork;     // I use "result" as undeclared variable
    delete(result,I,1); // result keep remain of the string
    GenVariant(aBase+aWork[I],result); // recursive call to iterate with remain of the string
    // first parameter keep characters extracted in previous iterations
.....

That's all. It more easy to understand under debugger watching on aBase and aWork parameters.

-----
Igor

PS: if you need not recursive logic then let me know.
0
 
LVL 1

Expert Comment

by:sageryd
ID: 2828649
Well....I can't exactly say I understood more of it when you explained but I guess I'll understand it when I debug it in Delphi. Great code though! Good work, Igor!

--johan
0
 
LVL 9

Expert Comment

by:ITugay
ID: 2828755
Hi all,
there is another one combinator (not recursive and standalone):


type

  TStrCombintor = class(TObject)
     fCNT : array of integer;
     fIDX : integer;
     procedure   Init(const V : string);
     procedure   RollData(var V : string; Index : integer);
     function    NextCombination(var V : string) : boolean;
  end;

......

procedure TStrCombintor.Init(const V : string);
begin
   SetLength(fCNT,length(V));
   fIDX:=0;
end;

procedure TStrCombintor.RollData(var V : string; Index : integer);
var I  : integer;
    C  : char;
begin
   C:=V[1];
   for I:=1 to Index+1 do V[I]:=V[I+1];
   V[Index+1]:=C;
end;

function TStrCombintor.NextCombination(var V : string) : boolean;
begin
    while fCNT[fIDX]>=fIDX+1 do
    begin
       RollData(V,fIDX+1);
       fCNT[fIDX]:=0;
       inc(fIDX);
    end;
    if fIDX < length(V)-1 then
    begin
      RollData(V,fIDX+1);
      inc(fCNT[fIDX]);
      fIDX:=0;
      result:=true;
    end else result:=false;
end;
---------------

and example how to use it:


procedure TForm1.SpeedButton1Click(Sender: TObject);
var SC : TStrCombintor;
    S  : string;
begin
  S  := '1234';
  SC := TStrCombintor.Create;
  SC.Init(S);
  repeat
    ListBox1.Items.Add(S);
  until not SC.NextCombination(S);
  SC.Free;
end;


-----
Igor
0
 
LVL 9

Expert Comment

by:ITugay
ID: 2832548
Hi,

and another one (not recursive):
-----

procedure MutateStr(S : string);
var C : array of integer;
    I : integer;
begin
   SetLength(C,Length(S)-1);
   I:=0;
   repeat
     insert(S[1],S,I+3);
     delete(S,1,1);
     inc(C[I]);
     if C[I]=I+2 then
     begin
       C[I]:=0;
       inc(I);
     end else
     begin
       I:=0;
       Form1.LB.Items.Add(S)
     end;
   until I = Length(S)-1;
end;

-----
It doesn't show initial combination, only all another. Do not pass string with length < 2;)
-----
Igor.
0
 
LVL 3

Expert Comment

by:wuyinzhi
ID: 2843963
hi igor, i tried your code above with Delphi 3 and found error at this line:

var C : array of integer;

i suppose you didn't put the index of array?

0
 
LVL 9

Expert Comment

by:ITugay
ID: 2844008
hi wuyinzhi,

this code for D5 you need to change

------OLD----- (D5)
var C : array of integer;
      I : integer;
begin
     SetLength(C,Length(S)-1);

----NEW---- (D3)
var C : array [0..255]  of integer;
      I : integer;
begin
     FillChar(C,SizeOf(C),#0);

------------

enjoy;)
-----
Igor
0
 

Expert Comment

by:JohnnyBoy
ID: 2853917
Isn't it


counter = length of data
for iLoop = 1 to counter
  answer = answer * counter
0
 
LVL 1

Author Comment

by:powerfool
ID: 2855366
hi JohnnyBoy, I don't think your "answer" is an answer for the question, please refer to ITugay's program, he's got best solution so far.

0
 
LVL 1

Expert Comment

by:sageryd
ID: 2855396
Why don't we end this thread? Igor has come up with many different variants of the code, propose an answer and end the thread, Igor!

--j exposing his thoughts...
0
 
LVL 9

Expert Comment

by:ITugay
ID: 2857716
I wouldn't like to propose an answer. May be another experts have interest solutions. And it's decigion of questioner to accept comment as answer.
;-)

Igor
0
 
LVL 1

Expert Comment

by:sageryd
ID: 2858504
Ok! I was just, as I said, exposing my current thought! ;o)

johan
0
 
LVL 1

Author Comment

by:powerfool
ID: 2863039
i already accepted igor's comment as right answer and gave my points. how could I do to lock this thread?
0
 
LVL 1

Expert Comment

by:sageryd
ID: 2863914
No you haven't!
0
 
LVL 9

Expert Comment

by:ITugay
ID: 2866553
hi powerfool,
If you like my answers then just click on "accept comment as answer" ;)
Igor.
0
 
LVL 1

Author Comment

by:powerfool
ID: 2879708
Comment accepted as answer
0
 
LVL 1

Author Comment

by:powerfool
ID: 2879709
Ok. I do it now.
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
Introduction Raise your hands if you were as upset with FireMonkey as I was when I discovered that there was no TListview.  I use TListView in almost all of my applications I've written, and I was not going to compromise by resorting to TStringGrid…
Along with being a a promotional video for my three-day Annielytics Dashboard Seminor, this Micro Tutorial is an intro to Google Analytics API data.
Microsoft Active Directory, the widely used IT infrastructure, is known for its high risk of credential theft. The best way to test your Active Directory’s vulnerabilities to pass-the-ticket, pass-the-hash, privilege escalation, and malware attacks …

813 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now