Saturday, 24 August 2013

Subset Algorithm

Subset Algorithm

let n describes cardinality of some set called A.
let m describes cardinality of subset of the A set.
if n = 4 and m = 1 => than we will get
n
‡" (x[i1]) = x[i1] + x[i2] + x[i3] + x[i4]
i1=1
if n = 4 and m = 2 => than we will get
n-1 n-1
‡" (x[i2] * (‡" (x[i1+1])) = x[1]*x[2] + x[1]*x[3] + x[1]*x[4] +
x[2]*x[3] + x[2]*x[4] + x[3]*x[4]
i1=1 i2=i1
if n = 4 and m = 3 => than we will get
n-2 n-2 n-2
‡" (x[ii] * (‡" (x[i2+1]) * (‡" (x[i3+2])) = x[1]*x[2]*x[3] +
x[1]*x[2]*x[4] + x[1]*x[3]*x[4] + x[2]*x[3]*x[4]
i1=1 i2=i1 i3=i2
if n = 4 and m = 4 => than we will get
n-3 n-3 n-3 n-3
‡" (x[ii] * (‡" (x[i2+1]) * (‡" (x[i3+2] * (‡" (x[i3+3]))) =
x[1]*x[2]*x[3]*x[4]
i1=1 i2=i1 i3=i2 i4=i3
as we can see the last step is function with one variable! so for all m as
a constant value we will get function with one variable. the question is
how can we mix these four steps in one expression?
Or how can we write a function with two variable?
As we saw the first variable is n. And second variable is m.
If it is possible to find out the expression f(n, m) with two variable,
then we can replace the oparetion * with another operation ;
also we can replace operation + with another operation U as Union operation.
And instead of gettion number of that two variable function there will be
another return type, actually it will be set.

No comments:

Post a Comment