11:24 a.m.
Dear Gretl Community,
I really stuck trying to define a function that gives a power set of a
set. Suppose I have a set S:
S = {"A", "B", "C"}
The associated power set, P(S), is:
P(S) = {{ }, {"A"}, {"B"}, {"C"}, {"A",
"B"}, {"A", "C"}, {"B", "C"},
{"A", "B", "C"}}
All that I can think by now (shame on me!) is this:
strings S = defarray("A", "B", "C")
scalar P_S_len = 2^nelem(S) # the size of the power set
strings P_S = array(P_S_len) # an array with 8 spaces.
Does anyone have any ideas?
Best,
Henrique Andrade
11:57 a.m.
On Mon, 22 Feb 2016, Henrique Andrade wrote:
Dear Gretl Community,
I really stuck trying to define a function that gives a power set of a
set. Suppose I have a set S:
S = {"A", "B", "C"}
The associated power set, P(S), is:
P(S) = {{ }, {"A"}, {"B"}, {"C"}, {"A",
"B"}, {"A", "C"}, {"B", "C"},
{"A", "B", "C"}}
All that I can think by now (shame on me!) is this:
strings S = defarray("A", "B", "C")
scalar P_S_len = 2^nelem(S) # the size of the power set
strings P_S = array(P_S_len) # an array with 8 spaces.
Does anyone have any ideas?
Maybe this is something you could build on:
<hansl>
strings S = defarray("A", "B", "C", "D")
scalar l = nelem(S)
matrix s = seq(0,2^l-1)'
matrix P = {}
scalar x = 2
loop l --quiet
a = s % 2
P ~= a
s = (s-a)/2
endloop
colnames(P,S)
print P
</hansl>
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------
2:16 p.m.
Dear Jack,
Thanks a lot for your help! I'm almost finishing my function and I'm
doing some performances comparisons with Python here on my Windows 7
PC (RAM: 8 GB; CPU: Core i5 3.2 GHz) and I think Hansl is not
performing well:
timeHansl = 64.698732
timePython = 0.67678400
Please take a look at the attached code (if you are interested ;-)).
Best,
Henrique
2:59 p.m.
On Mon, 22 Feb 2016, Henrique Andrade wrote:
Dear Jack,
Thanks a lot for your help! I'm almost finishing my function and I'm
doing some performances comparisons with Python here on my Windows 7
PC (RAM: 8 GB; CPU: Core i5 3.2 GHz) and I think Hansl is not
performing well:
timeHansl = 64.698732
timePython = 0.67678400
Never use $i, $j and so on in loops, unless you really need string
substitution. It prevents gretl from "compiling" your code.
If I rewrite your printing loop as
# look this up once, not n times
scalar cp = cols(P)
loop i = 1..rows(P) --quiet
loop j = 1..cp --quiet
if P[i, j] = 1
P_S = P_S ~ " " ~ S[j]
else
P_S = P_S ~ ""
endif
endloop
print P_S
P_S = ""
endloop
the hansl time on my machine drops from 22 seconds to 5.5. That's
against 0.65 for python, but then the itertools module is optimized
for just this sort of problem.
Allin
7:37 p.m.
On Mon, 22 Feb 2016, Allin Cottrell wrote:
On Mon, 22 Feb 2016, Henrique Andrade wrote:
> Dear Jack,
>
> Thanks a lot for your help! I'm almost finishing my function and I'm
> doing some performances comparisons with Python here on my Windows 7
> PC (RAM: 8 GB; CPU: Core i5 3.2 GHz) and I think Hansl is not
> performing well:
>
> timeHansl = 64.698732
> timePython = 0.67678400
Never use $i, $j and so on in loops, unless you really need string
substitution. It prevents gretl from "compiling" your code.
If I rewrite your printing loop as
# look this up once, not n times
scalar cp = cols(P)
loop i = 1..rows(P) --quiet
loop j = 1..cp --quiet
if P[i, j] = 1
P_S = P_S ~ " " ~ S[j]
else
P_S = P_S ~ ""
endif
endloop
print P_S
P_S = ""
endloop
the hansl time on my machine drops from 22 seconds to 5.5. That's against
0.65 for python, but then the itertools module is optimized for just this
sort of problem.
And besides, you can just scrap the "else" clause for your Hansl loop and
get some extra performance. After doing so, I too get an order of
magnitude of about 10:1, which isn't bad.
It's interesting to note that for smaller array sizes (say, if your
trim your array from 17 items to 12-13), hansl actually outperforms
Python, which I find very surprising.
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------
8:02 a.m.
Dear Jack and Allin,
Thanks a lot for your invaluable advices! I really couldn't figure out
these solutions and code improvements by myself.
Regards,
Henrique
8:36 a.m.
Am 23.02.2016 um 14:02 schrieb Henrique Andrade:
Dear Jack and Allin,
Thanks a lot for your invaluable advices! I really couldn't figure out
these solutions and code improvements by myself.
Let me pick up this old thread: Would it make sense to integrate such a
reasonably optimized powerset function into the extra.gfn package?
(which is now an addon)
thanks,
sven
9:04 a.m.
On Thu, 11 Oct 2018, Sven Schreiber wrote:
Am 23.02.2016 um 14:02 schrieb Henrique Andrade:
> Dear Jack and Allin,
>
> Thanks a lot for your invaluable advices! I really couldn't figure out
> these solutions and code improvements by myself.
>
>
Let me pick up this old thread: Would it make sense to integrate such a
reasonably optimized powerset function into the extra.gfn package? (which is
now an addon)
Sonds good to me.
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------
9:19 a.m.
Am 11.10.2018 um 15:04 schrieb Riccardo (Jack) Lucchetti:
On Thu, 11 Oct 2018, Sven Schreiber wrote:
> Am 23.02.2016 um 14:02 schrieb Henrique Andrade:
>> Dear Jack and Allin,
>>
>> Thanks a lot for your invaluable advices! I really couldn't figure out
>> these solutions and code improvements by myself.
>>
>>
>
> Let me pick up this old thread: Would it make sense to integrate such
> a reasonably optimized powerset function into the extra.gfn package?
> (which is now an addon)
Sonds good to me.
OK, which one is the final optimized version?
thanks,
sven
5:11 p.m.
On Thu, 11 Oct 2018, Sven Schreiber wrote:
Am 11.10.2018 um 15:04 schrieb Riccardo (Jack) Lucchetti:
> On Thu, 11 Oct 2018, Sven Schreiber wrote:
>
>> Am 23.02.2016 um 14:02 schrieb Henrique Andrade:
>>> Dear Jack and Allin,
>>>
>>> Thanks a lot for your invaluable advices! I really couldn't figure out
>>> these solutions and code improvements by myself.
>>>
>>>
>>
>> Let me pick up this old thread: Would it make sense to integrate such a
>> reasonably optimized powerset function into the extra.gfn package? (which
>> is now an addon)
>
> Sonds good to me.
>
OK, which one is the final optimized version?
If I'm not mistaken, this is more or less what we came up with in the end
<hansl>
function strings powerset(strings S)
matrix P = {}
scalar l = nelem(S)
scalar N = 2^l
matrix s = seq(0, N-1)'
loop l --quiet
matrix a = s % 2
matrix P ~= a
matrix s = (s-a)/2
endloop
strings PS = array(N)
loop i = 1..N --quiet
string c = ""
loop j = 1..l --quiet
if P[i, j]
c = c ~ " " ~ S[j]
endif
endloop
PS[i] = c
endloop
return PS
end function
# example
strings S = defarray("wage", "lwage", "belavg",
"abvavg", "exper",\
"looks", "union", "goodhlth", "black",
"female", "married", "south",\
"bigcity", "smllcity",
"service","expersq","educ")
set stopwatch
strings PwrSet = powerset(S)
printf "Elapsed time = %g\n", $stopwatch
</hansl>
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------
5:28 p.m.
On Thu, 11 Oct 2018, Riccardo (Jack) Lucchetti wrote:
If I'm not mistaken, this is more or less what we came up with in
the end
[...]
Actually, this is slightly faster:
<hansl>
function strings powerset(strings S)
scalar l = nelem(S)
scalar N = 2^l
matrix P = zeros(N,l)
matrix s = seq(0, N-1)'
loop i=1..l --quiet
matrix a = s % 2
matrix P[,i] = a
matrix s = (s-a)/2
endloop
strings PS = array(N)
loop i = 1..N --quiet
string c = ""
loop j = 1..l --quiet
if P[i, j]
c = c ~ " " ~ S[j]
endif
endloop
PS[i] = c
endloop
return PS
end function
</hansl>
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------
5:34 a.m.
Am 11.10.2018 um 23:28 schrieb Riccardo (Jack) Lucchetti:
On Thu, 11 Oct 2018, Riccardo (Jack) Lucchetti wrote:
> If I'm not mistaken, this is more or less what we came up with in the end
[...]
Actually, this is slightly faster:
<hansl>
function strings powerset(strings S)
scalar l = nelem(S)
scalar N = 2^l
matrix P = zeros(N,l)
matrix s = seq(0, N-1)'
loop i=1..l --quiet
matrix a = s % 2
matrix P[,i] = a
matrix s = (s-a)/2
endloop
strings PS = array(N)
loop i = 1..N --quiet
string c = ""
loop j = 1..l --quiet
if P[i, j]
c = c ~ " " ~ S[j]
endif
endloop
PS[i] = c
endloop
return PS
end function
</hansl>
Hi Jack, without having checked whether this is intended but the first
entry in the PwrSet string array is empty.
Artur
6 a.m.
Am 14.10.2018 um 11:34 schrieb Artur T.:
Hi Jack, without having checked whether this is intended but the first
entry in the PwrSet string array is empty.
Indeed I think conceptually the empty element must indeed be in the set
of all permutations. (Or at least there is such a convention.)
cheers,
sven
5:36 p.m.
On Sun, 14 Oct 2018, Sven Schreiber wrote:
Am 14.10.2018 um 11:34 schrieb Artur T.:
>
> Hi Jack, without having checked whether this is intended but the first
> entry in the PwrSet string array is empty.
Indeed I think conceptually the empty element must indeed be in the set of
all permutations. (Or at least there is such a convention.)
Exactly!
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------
1:58 p.m.
Am 14.10.2018 um 23:36 schrieb Riccardo (Jack) Lucchetti:
On Sun, 14 Oct 2018, Sven Schreiber wrote:
> Am 14.10.2018 um 11:34 schrieb Artur T.:
>>
>> Hi Jack, without having checked whether this is intended but the
>> first entry in the PwrSet string array is empty.
>
> Indeed I think conceptually the empty element must indeed be in the
> set of all permutations. (Or at least there is such a convention.)
Exactly!
Ah ok, thanks for the clarification.
Artur
6:22 a.m.
Am 22.02.2016 um 20:59 schrieb Allin Cottrell:
On Mon, 22 Feb 2016, Henrique Andrade wrote:
> Dear Jack,
>
> Thanks a lot for your help! I'm almost finishing my function and I'm
> doing some performances comparisons with Python here on my Windows 7
> PC (RAM: 8 GB; CPU: Core i5 3.2 GHz) and I think Hansl is not
> performing well:
>
> timeHansl = 64.698732
> timePython = 0.67678400
Never use $i, $j and so on in loops, unless you really need string
substitution. It prevents gretl from "compiling" your code.
That's interesting, I'm not sure if I had just forgotten about this or
if I never knew it. Is this advice mentioned somewhere (else)?
thanks,
sven
2162
days inactive
3128
days old
15 comments
5 participants
participants (5)
-
Allin Cottrell -
Artur T. -
Henrique Andrade -
Riccardo (Jack) Lucchetti -
Sven Schreiber