How to find combinations 1

[german12]

Hallo - greetings from Germany and sorry for my English (school knowledge only)

When I have a table like the following one (3 fields, 3 rows):

Record Car color Plant
----------------------------------------------------
1 Mercedes green A
2 VW yellow B
3 Ford black C

how can I write a program, which shows me all possible combinations (27 in this case) from
these few lines into a new table which should look like this:

Mercedes green A
Mercedes green B
Mercedes green C
Mercedes yellow A
Mercedes yellow B
Mercedes yellow C
Mercedes black A
Mercedes black B
Mercedes black C ....and so on, now with

VW green A
VW green B ......and then Ford.....so that you have filled 27 lines.

Would be great if this program could also do it automatically when the table has 4 or more
rows - but I would already be happy when I could find out, how the loops should be
programmed (perhaps putting each field-column into a separate array? But how in the hell
then to put it together?)

Thanks for any idea....
Klaus

 

[ramani]

HI
SELECT car from myTable INTO DBF tcar
SELECT color from myTable INTO DBF tcolor
SELECT plant FROM myTable INTO DBF tPlant
SELECT * FROM tCar, tColor, tPlant INTO CURSOR myCursor

myCursor has all what you want
Hope this helps you
ramani :-9
(Subramanian.G),FoxAcc, ramani_g@yahoo.com

 

[jimstarr]

Hi Klaus,

Ramani's way is brilliant.

Here's a more conventional approach:

SELECT car FROM myTable INTO ARRAY acar
SELECT color FROM myTable INTO ARRAY acolor
SELECT plant FROM myTable INTO ARRAY aplant

CREATE CURSOR OUTPUT (car c(10), color c(10), plant c(10))

FOR i = 1 TO ALEN(acar)
FOR j = 1 TO ALEN(acolor)
FOR k = 1 TO ALEN(aplant)
INSERT INTO OUTPUT VALUES(acar(i), acolor(j), aplant(k))
ENDFOR
ENDFOR
ENDFOR


Jim

 

[german12]

Thank you very much, Ramani and Jim. Both your hints are very valuable for me
As you know, one problem solved causes in most cases a new one:

How can I expand your program in that way that it automatically still works satisfying when e.g.
an additional column is added to the file mytable. (e.g. a fourth column oder let us say
there are 10 columns additional added - I would not prefer to write all the loops like
Jim did - and: also do not want to write down all the field names from mytable like ramani did.

I therefore tried this (and based on Ramani's program...and it worked so far....with a problem
for the last line which ramani had in his program....

*----------------
*Combinations
*---------------
close data
set safety off
clea
use mytable

*1.Step - create a file beginning with "t" plus
* the number of the loop-variable and fill
* that file with one field-column of mytable.dbf
* e.g. t1 = car, t2 = colour and so on.

for i = 1 to fcount()
t = "t"+alltrim(str(i)) &&Table to store a field-column
x = field(i)
select &x from mytable into dbf &t
select mytable
endfor

clea

*-----------------------------------------------------
*Second step - show the new tables created
*mytable is still in access
*-----------------------------------------------------
for i = 1 to fcount()
t = "t"+alltrim(str(i))
sele * from &t to screen
wait window "next file"
endfor

So far, I can save a lot of coding, when the file mytable gets bigger by columns.
All I still need is:
How can I automate now the last command which ramani had in his program?
It is the command: SELECT * from t1,t2,t3 into cursor mycursor.

Is it possible, to get this command by a loop which looks for files beginning with a "t" plus
the variable i and then create the above mentioned statement?

Look forward to a new good answer as the last one was, as I am an amateur only
If I ever come to the states I will bring german beer with me.....

Regards
Klaus

 

[german12]

*Meanwhile I found a simple solution to avoid re-programming when the column-counts
*expands in mytable - however it is only a quick shot.
*and by no way satisfying enough (imagine that you 256 colums filled in the source table)
*Regards
* Klaus


*Third step
*find out, how many field-columns the file mytable has
*and then do the equivalent select statement.
*Not satisfying - but it works
*(this sample works for 7 columns) - I am still thinking about
*a method which programms the equivalent statement by itself


fieldnos = fcount()
do case
case fieldnos = 1
Select * from t1 into cursor mycursor
case fieldnos = 2
Select * from t1,t2 into cursor mycursor
case fieldnos = 3
Select * from t1,t2,t3 into cursor mycursor
case fieldnos = 4
Select * from t1,t2,t3,t4 into cursor mycursor
case fieldnos = 5
Select * from t1,t2,t3,t4,t5 into cursor mycursor
case fieldnos = 6
Select * from t1,t2,t3,t4,t5,t6 into cursor mycursor
case fieldnos = 7
Select * from t1,t2,t3,t4,t5,t6,t7 into cursor mycursor
endcase

*Does anyone have a better idea?


selec mycursor
browse
close data

 

[nl]

Dear German12,
Both ramani and jimstarr 's idea are great.

You are using the right approach in counting number of fields of myTable. Here, I expand the idea in further.
Hope that it can help.



use myTable
n=fcount() && no. of fields in myTable
for i=1 to n
select myTable
c=alltrim(field(i)) && field name: car, color, plant, etc.
r='T'+alltrim(str(i)) && cursor name : T1, T2, T3, etc.
select &c from myTable into cursor &r
endfor

t=''
for i=1 to n
t=t+',t'+alltrim(str(i)) && table name :,T1 ,T2 ,T3, etc.
endfor
t=substr(t,2) && remove leading comma

select * from &t into cursor myCursor
select myCursor
browse

Norman.

 

[ramani]

Hi German

********************************************************
** Prg to DISPLAY POSSIBLE COMBINATION OF FIELDS
** Author ... Subramanian. G
** Contribution to TEK-TIP Forum
**
** PRG NAME ... GetCombination.PRG
** How Run ... DO GetCombination WITH myTable
** ... =GetCombination(myTable)
********************************************************
PARAMETERS myTable

IF EMPTY(myTable)
RETURN
ENDIF

LOCAL myList, myCursor, i, myCursor1
myList = ""
myCursor = "Cursor"

USE (myTable) IN 0 AGAIN ALIAS myTable
FOR I=1 TO FCOUNT()
myCursor1 = myCursor+ALLTRIM(STR(i))
IF I > 1
myList = myList+","+myCursor1
ELSE
myList = myCursor1
ENDIF
myHead = FIELD(i)
SELECT EVALUATE(FIELD(I)) AS (myHead) ;
FROM (myTable) INTO CURSOR (myCursor1)
SELECT myTable
ENDFOR
USE

SELECT * FROM &myList INTO CURSOR myCursor

BROWSE
********************************************************
** EOF()
** Ramani, (Subramanian.G, FoxAcc, ramani_g@yahoo.com)
********************************************************
**
Hi Norman.. same idea... I need not have wasted my time, had I seen your code earlier... Anyway that I have coded, ended it here.
ramani :-9
(Subramanian.G),FoxAcc, ramani_g@yahoo.com

 

[german12]

Hi

I had a lot of fun to see and to think over what you guys (Ramani, Jim and Norman) found out to combine columns of a table, and I learned a lot due to the very interesting and flexible approaches you started.

Finally I have the excact solution I wanted now and would like to thank you very much - this is not the last time that I am here - I promise.
Now I am thinking of a similiar problem which has also to do with combinations, but perhaps the solution is
is another one.

I want to create a new word from an existing one (e.g. to find a new BRANDMARK)

Let us take the word MOTHER.

We have in mathematical sense to do with permutations and could have (if there a no letters to be repeated)
other creations like THERMO, REHTMO and so on.

The number of possible combinations in this case (no repeating letters) is the faculty of 6 elements (letters) which = 6! and therefore 1 * 2 * 3 * 4 * 5 * 6 = 720 possibilities.

In case that some letters could repeat (like the word 122) the possibilities will be reduced as you have a double
" 2 " in 122 - however I would prefer to ignore this and - after a program has run
and has build a list one could select a new query using this list and filter unique redords only by
using the SELECT DISTINCT ....SQL command..

By the way: The unique possibilities to mix the word 122 are 3 as there are: 122,212,221 and are calculated
by the faculty of elements (n=3) divided by the faculty of the number of repeated elements which are 2 here.
So the number of combinations for 122 are (1*2*3) divided by (1*2) = 3.

I do think of another program as we have so far, as that program is based on columns in a single table to mix,
however here there is no table but a few letters in a word only.

I think there has a new approach to be made......has anyone again a good idea?

But caution - if you have a long word like e.g. ABCDEFGHIJKLMNOPQRSTUVWXYZ the combinations
will grow to the faculty of 26!, smile....

KLaus

 

[jimstarr]

Hi Klaus,

Here's a crude function which will do permutations of words up to 9 characters in length. It's slow for words over 6 characters.

=permute('abdb')

******************************
FUNCTION permute

LPARAMETER wordx

CREATE CURSOR cc (theword c(20))

lenx = LEN(wordx)

lowx = lowperm(wordx) && lowest permutation of the word

strx = ''
prevx = SPACE(1)
j = 0
FOR i = 1 TO lenx
IF SUBSTR(lowx, i, 1) != prevx
j = j + 1
ENDIF
strx = strx + ALLTRIM(STR(j))
prevx = SUBSTR(lowx, i, 1)
ENDFOR

FOR i = 1 TO 10 ** lenx && loop thru all possible numbers
ii = ALLTRIM(STR(i, lenx))
jj = lowperm(ii)
IF jj == strx
INSERT INTO cc VALUES(putback(ii, wordx))
ENDIF
ENDFOR

SELECT cc
BROWSE

******************************
FUNCTION lowperm && lowest permutation of the parameter
LPARAMETER wordx

DIMENSION arrayx( LEN(wordx))

FOR k = 1 TO ALEN(arrayx)
arrayx(k) = SUBSTR(wordx, k, 1)
ENDFOR

=ASORT(arrayx)

resx = ''
FOR k=1 TO ALEN(arrayx)
resx = resx + arrayx(k)
ENDFOR

RETURN resx

******************************
FUNCTION putback && translate digits back to letters

LPARAMETER word1, word2

resxx = ''
FOR l = 1 TO LEN(word1)
valx = VAL(SUBSTR(word1, l, 1))
resxx = resxx + SUBSTR(word2, valx, 1)
ENDFOR

RETURN resxx


Jim

 

[chpicker]

Call me crazy, but I figured this could be handled most efficiently with a recursive function. So, I wrote one. As the length of the word grows, the time to calculate it grows exponentially, as you can see by these numbers:

4 letters: 24 results, 0.001 seconds
5 letters: 120 results, 0.004 seconds
6 letters: 720 results, 0.026 seconds
7 letters: 5040 results, 0.179 seconds
8 letters: 40320 results, 1.581 seconds
9 letters: 362880 results, 14.884 seconds

The function can take as many letters as the stack permits. I believe VFP allows up to 27 nested function calls, so it will depend on how many have already been called before it hits this function. I wouldn't suggest trying more than 9, though. FYI, the above times were calculated on a P3-666MHz running Win2k.

function permute(cWord)
	nLen=len(cWord)
	create cursor wordlist(word c(nLen))

	nStart=seconds()
	recurse("",UPPER(cWord))
	nTotal=seconds()-nStart
	goto top
	browse nowait
	return nTotal
endfunc

function recurse(cStart,cRest)
	&&This function steps through all possible
	&&combinations of the letters of a word by
	&&recursively calling itself with smaller segments
	local cBegin,cEnd,i
	if len(cRest)>1
		for i=1 to len(cRest)
			cBegin=cStart+substr(cRest,i,1)
			cEnd=left(cRest,i-1)+substr(cRest,i+1)
			recurse(cBegin,cEnd)
		next
	else
		insert into wordlist (word) values (cStart+cRest)
	endif
endfunc

 

[DEDMOD]

BTW, if you want something which has some real value, as opposed to simply words like 'dsrwo' it would probably be best to fnd a word dictionary (search the web for 'scrabble' for instance. Then select all the words of particular lengths and code them for vowels and consonants. Thus 'particular' would give you 'cvccvcvcvc'. Produce a list of all these skeletons and how many of each there are in a table. Now when you have a word you want to permutate, count the vowels and consonents and permutate them separately. Then print a list of say the top 10 or 100 formats of this type using a particular permutation and move on to another permutation. This will both make the program run much faster since it will be the sum of two shorter permutation, and will only produce words which have some resemblance to real words.

This should work just as well in German as in English, though if you get some of those really long German combinations it may still be slow. My favorite German word is Das Morgansonnenschein (spelling something like that. Morning Sunshine for those knowing no German).

Dave Dardinger