kombinacie :: Something smarter than us is going to emerge


node:	kombinacie
template:	4
parent:	Python Programming Language
owner:	mimmon
viewed by:
created:	14.08.2009 - 14:59:51

cwbe coordinatez:
101
63540
2076399
856608
4857954

ABSOLUT
KYBERIA

permissions
you:	r,
system:	public
net:	yes

Hladam algoritmus, ktoreho vystupom budu vsetky kombinacie prvkov listu s n prvkami.
Teda aby pri dvoch prvkoch v liste [0,1] vratil [0, 1, 01]
a pri styroch prvkoch [0,1,2,3] vratil [0,1,2,3,01,02,03,12,13,23,012,013,023,123,0123]

z pascalovho trojuholnika viem zistit, kolko bude m-prvkovych kombinacii, dokonca aj kolko kombinacii bude zacinat 0, kolko 1 a podobne, ale neviem urobit elegantne vseobecne riesenie.

Nemate niekto nieco take? Alebo mi prenechate radost z objavovania? :)

000001010006354002076399008566080485795404858427

heh, K namiesto zimanovi som udelil sebe a to mi dokonca este vypisalo ze uz to nemam hulit.. ved este nie je tak neskoro..

00000101000635400207639900856608048579540485842704858492

tak to uz nehul! :P

000001010006354002076399008566080485795404858151

ziman 14.08.2009 - 16:57:19 (modif: 14.08.2009 - 16:58:39), level: 1, UP NEW !!CONTENT CHANGED!!

Re: kombinacie

Vypocet v zoznamovej monade:

>>> import operator

>>> concat = lambda xs: reduce(operator.concat, xs, [])

>>> fm = lambda p,xs: [[]] if not xs else concat([map(lambda y: [xs[0]]+y, fm(p,xs[1:])) if b else fm(p,xs[1:]) for b in p(xs[0])])

>>> fm(lambda _: [True, False], [1,2,3,4])

[[1, 2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 2], [1, 3, 4], [1, 3], [1, 4], [1], [2, 3, 4], [2, 3], [2, 4], [2], [3, 4], [3], [4], []]

Specializovanejsi postup:

>>> fm = lambda xs: [[]] if not xs else map(lambda y: [xs[0]]+y, fm(xs[1:])) + fm(xs[1:])

>>> fm([1,2,3,4])

[[1, 2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 2], [1, 3, 4], [1, 3], [1, 4], [1], [2, 3, 4], [2, 3], [2, 4], [2], [3, 4], [3], [4], []]

00000101000635400207639900856608048579540485815104858210

ziman 14.08.2009 - 17:36:34 (modif: 14.08.2009 - 17:38:02) [4K] , level: 2, UP NEW !!CONTENT CHANGED!!

Re[2]: kombinacie

este ma napada, ze by sa to dalo mierne upravit takto:

fm = lambda x: [[x[0]]+y for y in fm(x[1:])] + fm(x[1:]) if x else [[]]

co je trochu strucnejsie

0000010100063540020763990085660804857954048581510485821004858425

tak tomuto hovorim elegantne riesenie.. vdaka

este si to vyskusam (nie som na svojom pocitaci, nemam tu python), musim vidiet na vlastne oci, ze to bezchybne funguje.. :)

ale opat obdivujem moznosti, co ponuka lambda

000001010006354002076399008566080485795404858151048582100485842504858491

A inak, velmi som ti nepomohol, pretoze som ti prezradil rovno riesenie, bral som to skor ako taku zabavku pre seba.

Skus ale z neho vycitat, ako to funguje a preco, co ten zapis znamena.

00000101000635400207639900856608048579540485815104858210048584250485849104858530

myslim, ze som to pochopil, ide viac-menej o riesenie pomocou rekurzie.. a urcite si aj sam vyskusam vyrobit tu funkciu.. ja to beriem tiez ako zabavku, hoci jej aplikaciu aj realne vyuzijem

0000010100063540020763990085660804857954048581510485821004858425048584910485853006386100

mimmon 14.12.2011 - 16:08:57 , level: 6, UP NEW

Re[6]: kombinacie

prvocisla

def divi(a):

  for i in range(2,int(sqrt(a))+1):

    if not a%i: return [i]+divi(a/i)

  return [a]

000001010006354002076399008566080485795404858151048582100485842504858491048585300638610006452945

Python (cpython aspon) ma defaultne dost nizky limit na rekurziu (1000), takze radsej by som sa rekurzii vyhol v pripadoch, kde na ten limit mozes narazit. To len tak mimochodom. Pripadne sa da zmenit pomocou sys.setrecursionlimit() ale neviem aky to ma dopad na performance.

edit: a tiez pouzivaj xrange namiesto range ak to pises v python 2.x; xrange vracia generator co je setrnejsie ak a) nepotrebujes celu sekvenciu b) sekvencia je fakt velka. v python 3.x uz range vracia generator

00000101000635400207639900856608048579540485815104858210048584250485849104858530063861000645294506458244

dakujem za tip

taketo prakticke rady a usmernenia by som potreboval castejsie :)

000001010006354002076399008566080485795404858151048582100485842504858481

ziman 14.08.2009 - 21:16:34 (modif: 14.08.2009 - 21:20:33), level: 4, UP NEW !!CONTENT CHANGED!!

Re[4]: kombinacie

na to nepotrebujes lambdu :)

def fm(x): return [[x[0]]+y for y in fm(x[1:])] + fm(x[1:]) if x else [[]]

len som to tam tak nejak zo zotrvacnosti...

0000010100063540020763990085660804857954048581510485821004858334

sick :)

000001010006354002076399008566080485795404857983

v pythone neviem robit, ale

imho to je ako binarne cislo, kde kazdy rad je jedna cifra z listu, teda:
3210
--------------------
0000 - prazdne
0001 - 0
0010 - 1
0011 - 01 (10)
0100 - 2
0101 - 02
0110 - 12
0111 - 123
1000 - 3
atd

nemam cas, takze narychlo v c++ by to bolo asi takto (max 64 cifier):

zoznam_kombinacii sprav_z(vector<int>& v)
{
int val = (1 << v.size()) - 1; // vsetky prvky pouzite (11111..)

while (val != 0)
{
for (int i=63; i>0; i--)
{
if (val & (1<<i))
kombinacia.add( i );
}

zoznam_kombinacii.add( kombinacia );
val--;
}

return zoznam_kombinacii;
}

ehm, int je akoze 64-bitovy ;)

nejak obdobne by to malo ist spravit aj bez takeho lowlevel

00000101000635400207639900856608048579540485798304858434

zimanove riesenie je sice elegantne, ale toto tvoje sa mi tiez paci, je strasne jednoduche, co sa tyka logiky