Challenge ! Can Anyone Solve This One!

[GlynW]

I need to write a fox prog to display every possible combination of stored records in a table possible. The trick is to show every combination without duplicating or missing combinations.

for example:

Cursor BOB
Rec1 A
Rec2 B
Rec3 C
Rec4 D

The result should be 15 combinations (I think!) they can be in any order)
AB counts the same as BA and so does not count as a combination. Also there could be any number of Records (so I expect the code to run slowly)

An example of the results

Combi 1 A
Combi 2 AB
Combi 3 ABC
Combi 4 A C
Combi 5 ABCD
Combi 6 AB D
Combi 7 A CD
Combi 8 A D
Combi 9 B
Combi 10 BC
Combi 11 B D
Combi 12 BCD
Combi 13 C
Combi 14 CD
Combi 15 D

I've tried writting a program using recursion but, it keeps missing out "AB D" DOH!

This is a real brain teaser (or Head F**K), so any help would be appreciated.

Cheers
Glyn

 

[DannC]

Try with backtracking. It will work, for sure .

 

[Guest_imported]

Backtracking?!?!?! woz that?

Do you mean working up from the bottom of the table rather from the top? If so wouldn't i get the same problem but with 'A CD' missing instead of 'AB D'. Or do you mean using trace to find out why some are missing?

What I really need is to see if there is a simplier recursive routine I can use instead of my monster code!

Cheers

Glyn

 

[Shanachie]

The key to this is that you have 2**nrecs combinations to evaluate. Each record is either in the combo or out. You're going to generate vast numbers of combos with any sizeable table. For example, with 32 records, you've got 2**32 combinations (less the one comprised of "all records out&quot, or 4.3 billion. Keep in mind that if you can evaluate say, 10,000 records each second, you'll need 430,000 seconds to try all combos. That's 119 hours! And the number of combos and the time double with each additional record. So 36 records will require 1908 hours, about 80 days.

You may want to rethink your algorithm. <g>

ShanachieQ

 

[geralyn]

Here's the start of an idea as I haven't fully thought it through, but it might help

Try creating as many duplicate tables as you have records.

Be sure to have a blank record in each.

 

[jimstarr]

Hi Glyn,

Without getting into it very deeply here are some thoughts.

1. Create a loop from 1 up to 2**n where n = the number of records, e.g. FOR i = 1 to 2**n

2. Create a routine which would convert i to a character string representing its binary value, e.g. 5 = '101'.

3. Assign each record value a position in the &quot;bit&quot; string, and insert the value if '1', blank if '0'.

This, I think, will produce all combinations. Good luck!

Jim

 

[GlynW]

Cheers for your ideas, but I'm still having problems

Shanachie, your right it will be a nightmare, but In reality the program will only deal with between 2 and 5 records and no more, anything above five records I would supress and display a message.


This is what I have so far... If anyone wants to cut and paste this test code to see what I'm trying to do it'll be cool...
What am I doing wrong?.. trying to get my head round this is driving me mad!!!


CREATE CURSOR Payments (PayRec C(1))

SELECT Payments
APPEND BLANK
REPLACE PayRec WITH &quot;A&quot;
APPEND BLANK
REPLACE PayRec WITH &quot;B&quot;
APPEND BLANK
REPLACE PayRec WITH &quot;C&quot;
APPEND BLANK
REPLACE PayRec WITH &quot;D&quot;

CLEAR
SET TALK OFF
SET ECHO OFF


*********** START OF CODE ************
SELECT PAYMENTS
T_TotalRecs = RECCOUNT()

T_space = 0
T_RecNo = 0
T_Combi = &quot;&quot;
T_Elements = 0
T_Count = 0

SELECT Payments
GOTO TOP
DO WHILE .NOT. EOF(&quot;Payments&quot
T_RECNO = RECNO()

T_Elements = T_Elements + 1
T_Combi = PayRec
T_Count = T_Count + 1
? t_count, T_Elements,T_Space, T_Space,T_Combi
DO GETVAL

SELECT Payments
GOTO T_RECNO
SKIP
ENDDO
RETURN


PROCEDURE GETVAL
FOR T_Loop1 = 1 TO T_TotalRecs
SELECT Payments
GOTO T_RECNO
T_Combi = PayRec

SKIP T_Loop1
DO WHILE .NOT. EOF(&quot;Payments&quot
T_Combi = T_Combi + PayRec
T_Count = T_Count + 1
? t_count, T_Elements, T_Loop1,T_Loop1, T_Combi
SELECT Payments
SKIP
ENDDO
NEXT T_Loop1
RETURN

 

[GlynW]

ALL STOP!!!!!!

rgbean (Programmer) was an absolute star, and sent me example of code what would help me out, and it works a treat!

Thanks everyone for your help


I am a happy man!

Cheers

Glyn

 

[JimmyK]

Hi,
This is another solution without recursion procedure (stack overflowed )

clos data
set safe off

create table ONE (mot C(1) )

&& Insert A,B,C,D
for i = 65 to 68
insert into ONE(mot) Values(chr(i))
endfor

sele 0
CREATE table TWO( chuoi C(50)) && contain results

sele ONE
n = recc()

for i =1 to n
=ChinhHop(i)
endfor



*************************
Proc ChinhHop
lpara sophantu


if sophantu<=1
sele mot as chuoi from ONE into dbf Add123
sele TWO
appe from Add123
retu
endif


duoi = sophantu - 1

sele ONE
_char=[]

go top

do while !eof([ONE])

_rcn = recn()
_char = _char+ONE.mot
_char2 = ONE.mot
select _char2+allt(chuoi) as chuoi1 from TWO;
into dbf Add1231 ;
where len(allt(chuoi))= duoi and (not (left(chuoi,1)$_char))

sele chuoi1 as chuoi from Add1231 into dbf Add123

sele TWO
appe from Add123

sele ONE
go _rcn
skip

enddo

Retu





Jimmy Le
nhan_tiags@yahoo.com

 

[JimmyK]

Hi Glyn,

Your program generates NOT ENOUGH results. pls check my solution.
If you insert A B C D E F G ,.. it also generates ENOUGH results
Jimmy Le
nhan_tiags@yahoo.com

 

[weedz]

I guess you will have to check your old statistcal math books from school. These problems are easily solved with the right formulas.
Before trying to reinvent the wheel, I guess there should be some nice algorithms on the web that can help you on your way.

HTH,
Weedz (Wietze Veld)
My private project:

http://www.crowncap.demon.nl\info\crwnbase

And especially for VFP rookies:

http://fox.wikis.com/wc.dll?Wiki~VFPRookieMistakes~VFP