Alle mogelijkheden voor een binomiaal probleem

[jhnbk]

Stel ik heb een n aantal variabelen (uiteraard voorgesteld in een array). Elk van deze variabelen heeft één coëfficiënt die 0 of 1,5 kan zijn. Ik zou dus al deze mogelijkheden moeten kunnen genereren om zodoende de maximale combinatie te weten. (Ter info: het berekenen van de waarde uit zulke reeks ligt niet voor de hand en doet niet ter zake voor dit probleem)

Ik had gedacht; indien er n variabelen zijn; dan zijn er 2ⁿ mogelijkheden en dan volstaat het om binair te tellen van 0 tot 2ⁿ en dan voor een 0 de eerste en voor een 1 de tweede coëfficiënt te gebruiken. Klopt dit of zijn er andere, efficiëntere, methoden?

[Vladimir Lenin]

Dat is volkomen correct, en volgens mij is het onmogelijk om een lagere comlexiteit dan

\(O\left(2^n\right)\)

te bekomen. Nou volgens mij kan je het best binair tellen doormiddel van bijvoorbeeld een uint (indien n < 32) of ushort (n < 64) en vervolgens de booleaanse waarde uit deze variabele extracteren d.m.v. bitgewijze AND operator en bitgewijze verschuiving. Om bijvoorbeeld de 3de waarde eruit te halen:

\(\begin{verbatim}byte c1 = ((x & 8)>>3);\end{verbatim}\)

of dus voor waarde i:

\(\begin{verbatim}byte ci = ((x & 2^i)>>i);\end{verbatim}\)

[jhnbk]

Thx! Ik ga er eens naar kijken wat ik er van kan maken in C#.

[Vladimir Lenin]

Het hoeft niet noodzakelijk in C#, Java ondersteund ook dergelijke bitgewijze operatoren. Verder nog even een foutje rechtzetten. Met

\(\verb+2^i+\)

bedoelde ik niet niet de bitgewijze or, maar

\(2^i\)

de wiskundige machtsverheffing, maar ik stond er even niet bij stil, dat dit verkeerd was. Excuses.