|
Home > Archive > Programming with dBASE > December 2006 > Formula for calculating permutations
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Formula for calculating permutations
|
|
| Robert Bravery 2006-12-07, 5:20 am |
| HI all,
I have a table of values that I have to sort of pivot. But I need to
caluclate the ammount of rows that it will generate
The table has 5 possible value combinations (as columns)
so:
if I have
apples
oranges
bananas
as one value combination
my pivoted row would look like
null null null null null
apple null null null null
oranges null null null null
bananas null null null null
but
apples
oranges
bananas
and:
man
women child
then
null null null null null
apple null null null null
oranges null null null null
bananas null null null null
apple man null null null
oranges man null null null
bananas man null null null
apple woman null null null
oranges woman null null null
bananas woman null null null
apple child null null null
oranges child null null null
bananas child null null null
null man null null null
null woman null null null
null child null null null
and if I had:
apples
oranges
bananas
pears
peaches
man
woman
child
brother
sister
home
work
play
school
shop
then
null null null null null
apple null null null null
oranges null null null null
bananas null null null null
pears null null null null
peaches null null null null
apple man null null null
oranges woman null null null
bananas child null null null
pears brother null null null
peaches sister null null null
null man null null null
null woman null null null
null child null null null
null brother null null null
null sister null null null
apple man home null null
oranges woman work null null
bananas child play null null
pears brother scholl null null
peaches sister shop null null
null man home null null
null woman work null null
null child null play null
null brother school null null
null sister shop null null
null null home null null
null null work null null
null null null play null
null null school null null
null null shop null null
apple null home null null
oranges null work null null
bananas null play null null
pears null scholl null null
peaches null shop null null
and so forth antill all possible combinations of five colums are fille. Keep
in mind that I am not linited to 5 values per segment, I could have any
numerb of values per segmant but only linited to 5 segments as there are 5
possible column values
so I could have
apples
oranges
bananas
pears
peaches
naartjies
watermealon
grapefruite
strawberry
etc
etc
etc
Thnks Hope the explanation was good
Robert
| |
| Roland Wingerter 2006-12-07, 5:20 am |
| Hi Robert,
check out crossProd.prg in the dUFLP, it does something very similar.
set proc to :dUFLP:crossprod.prg addi
aResult = crossProd(& #123;'apple','orange
','banana'},& #123;'man','woman','
child'})
do:dUFLP:disparray with aResult
Roland
Robert Bravery wrote
>
> I have a table of values that I have to sort of pivot. But I need to
> caluclate the ammount of rows that it will generate
> The table has 5 possible value combinations (as columns)
> so:
> if I have
> apples
> oranges
> bananas
> as one value combination
> my pivoted row would look like
> null null null null null
> apple null null null null
> oranges null null null null
> bananas null null null null
> but
>
> apples
> oranges
> bananas
>
> and:
> man
> women child
>
> then
> null null null null null
> apple null null null null
> oranges null null null null
> bananas null null null null
> apple man null null null
> oranges man null null null
> bananas man null null null
> apple woman null null null
> oranges woman null null null
> bananas woman null null null
> apple child null null null
> oranges child null null null
> bananas child null null null
> null man null null null
> null woman null null null
> null child null null null
| |
| Roland Wingerter 2006-12-07, 5:20 am |
| Robert Bravery wrote
>
> I have a table of values that I have to sort of pivot. But I need to
> caluclate the ammount of rows that it will generate
-----
If you just need the amount of rows, try this as an example:
a1 = new array(3) // set 1
a2 = new array(5) // set 2
? (a1.size+1) * (a2.size+1)
Roland
| |
| Michael Nuwer 2006-12-07, 7:12 pm |
|
Let n be the count of the number of words plus 5 (for nulls)
Let k be 5 (for the number of columns)
Then a permutation is:
n!
n_P_k = --------
(n - k)!
where "!" is a factorial:
1 * 2 * ... * n
Something like this in code
n2=1
for i=1 to n
n2=n2*i
next
k2 = 1
for i=1 to n-5
k2=k2*i
next
nOfRows = n2/k2
Robert Bravery wrote:
> HI all,
>
> I have a table of values that I have to sort of pivot. But I need to
> caluclate the ammount of rows that it will generate
> The table has 5 possible value combinations (as columns)
> so:
> if I have
> apples
> oranges
> bananas
> as one value combination
> my pivoted row would look like
> null null null null null
> apple null null null null
> oranges null null null null
> bananas null null null null
> but
>
> apples
> oranges
> bananas
>
> and:
> man
> women child
>
> then
> null null null null null
> apple null null null null
> oranges null null null null
> bananas null null null null
> apple man null null null
> oranges man null null null
> bananas man null null null
> apple woman null null null
> oranges woman null null null
> bananas woman null null null
> apple child null null null
> oranges child null null null
> bananas child null null null
> null man null null null
> null woman null null null
> null child null null null
>
> and if I had:
>
> apples
> oranges
> bananas
> pears
> peaches
>
> man
> woman
> child
> brother
> sister
>
> home
> work
> play
> school
> shop
>
> then
>
> null null null null null
> apple null null null null
> oranges null null null null
> bananas null null null null
> pears null null null null
> peaches null null null null
> apple man null null null
> oranges woman null null null
> bananas child null null null
> pears brother null null null
> peaches sister null null null
> null man null null null
> null woman null null null
> null child null null null
> null brother null null null
> null sister null null null
> apple man home null null
> oranges woman work null null
> bananas child play null null
> pears brother scholl null null
> peaches sister shop null null
> null man home null null
> null woman work null null
> null child null play null
> null brother school null null
> null sister shop null null
> null null home null null
> null null work null null
> null null null play null
> null null school null null
> null null shop null null
> apple null home null null
> oranges null work null null
> bananas null play null null
> pears null scholl null null
> peaches null shop null null
>
> and so forth antill all possible combinations of five colums are fille. Keep
> in mind that I am not linited to 5 values per segment, I could have any
> numerb of values per segmant but only linited to 5 segments as there are 5
> possible column values
>
> so I could have
>
> apples
> oranges
> bananas
> pears
> peaches
> naartjies
> watermealon
> grapefruite
> strawberry
> etc
> etc
> etc
>
> Thnks Hope the explanation was good
>
> Robert
>
>
>
>
>
>
| |
| Eric Logan 2006-12-07, 7:12 pm |
| To point out something interesting about the permutation formula:
'Permutations' deals with the different orders into which you can arrange
sets of things, and the number of distinct sets that you are arranging.
The number of distinct sets of k elements that you can draw from n elements
could be written; Combinations(k, n). Calculation: Combinations(k,n) =
(n!)/(((n-k)!)*(k!)).
The k elements in each combination can be arranged in k! different orders
(permutations).
So permutations(k,n) = (k!)*combinations(k,
n) = (k!) * (n!)/(((n-k)!)*(k!))
= (n!)/((n-k)!).
So permutations relate to combinations in a simple way.
E.L.
"Michael Nuwer" wrote ...
> Let n be the count of the number of words plus 5 (for nulls)
> Let k be 5 (for the number of columns)
> Then a permutation is:
> n!
> n_P_k = --------
> (n - k)!
>
> where "!" is a factorial:
> 1 * 2 * ... * n
>
> Something like this in code
>
> n2=1
> for i=1 to n
> n2=n2*i
> next
>
> k2 = 1
> for i=1 to n-5
> k2=k2*i
> next
>
> nOfRows = n2/k2
>
>
| |
| Robert Bravery 2006-12-07, 7:12 pm |
| Well thanks a lot everyone,
But my "permutations would not be like that, there will always be one order.
So set one can only go into column one, and set two can only go into column
two
So if we had {"one","two"}, {"four",five"}
the first set will always go into the forst column ans the second set into
the second column etc
the eventual arangement would only be
one, null
two,null
one,four
two,four
one,five
two,five
null,four
nul,five
null,null
do this seems to be (n+1)*(n+1) ...n
Thanks
Robert
"Eric Logan" <jelogan@pcweb.net> wrote in message
news:AOVUOdjGHHA.1524@news-server...
> To point out something interesting about the permutation formula:
> 'Permutations' deals with the different orders into which you can arrange
> sets of things, and the number of distinct sets that you are arranging.
> The number of distinct sets of k elements that you can draw from n
elements
> could be written; Combinations(k, n). Calculation: Combinations(k,n) =
> (n!)/(((n-k)!)*(k!)).
> The k elements in each combination can be arranged in k! different orders
> (permutations).
> So permutations(k,n) = (k!)*combinations(k,
n) = (k!) *
(n!)/(((n- k)!)*(k!))
> = (n!)/((n-k)!).
> So permutations relate to combinations in a simple way.
> E.L.
>
> "Michael Nuwer" wrote ...
>
>
>
| |
| Rick Gearardo 2006-12-07, 7:12 pm |
| That's exactly what it would be.
"Robert Bravery" <me@u.com> wrote in message
news:EyZZYIkGHHA.1140@news-server...
> Well thanks a lot everyone,
> But my "permutations would not be like that, there will always be one
> order.
> So set one can only go into column one, and set two can only go into
> column
> two
> So if we had {"one","two"}, {"four",five"}
> the first set will always go into the forst column ans the second set into
> the second column etc
> the eventual arangement would only be
> one, null
> two,null
> one,four
> two,four
> one,five
> two,five
> null,four
> nul,five
> null,null
>
> do this seems to be (n+1)*(n+1) ...n
>
> Thanks
> Robert
>
>
>
> "Eric Logan" <jelogan@pcweb.net> wrote in message
> news:AOVUOdjGHHA.1524@news-server...
> elements
> (n!)/(((n-k)!)*(k!))
>
>
| |
| Eric Logan 2006-12-07, 7:13 pm |
|
"Robert Bravery" wrote ...
> So set one can only go into column one, and set two can only go into
column two.
{"one","two"}, {"four",five"}
Say set A is in one field, set B is in a different field, etc. It sounds as
though you want something like a cartesian (unconstrained) join between all
distinct values in A, all distinct values in B, etc, for all fields (sets).
I often do something like that for standardizing 'ragged' data for graphing.
I make a cartesian join of the full possible ranges of the 'label' fields
(month, area, etc), and then join the existing data to it. This standardizes
data to make it easier to create a sequence of graphs that all have the same
range of X axis values, and the same number of data series' and data points.
Where there is no data that section of line or bar is blank on the chart.
E.L.
| |
| Roland Wingerter 2006-12-08, 7:13 pm |
| Robert Bravery wrote
> Well thanks a lot everyone,
>
> seems to be (n+1)*(n+1) ...n
-----
I agree. Glad you solved it.
Roland
|
|
|
|
|