Compound Enumeration (that's a term I just made up, forgive me)

[Guv]

First: there is no reason to omit one from the powers of two.

Convert the number (EG: 1090) to binary, and use positions of the one bits as a subscripts into an array containing the data about the furniture ordered.

To convert an integer to binary, use a loop with Mod Function and division by two. This will indicate one bits starting with least significant. If number Mod 2 is not zero, least signifciant bit is one. Then subtract one and divide by two. If result Mod 2 is not zero, next bit is one. Et cetera.

Above is a sloppy description of the process, but you should get the general idea.

[aknisely]

Okay, after spending two hours trying to figure out what all that means, I have to hang my head in defeat. I... don't... get it

[Nucleus]

If 1090 And 2 = 2 Then MsgBox "chair"
If 1090 And 4 = 4 Then MsgBox "couch"
If 1090 And 8 = 8 Then MsgBox "Wicker chair"
If 1090 And 64 = 64 Then MsgBox "sofa"
If 1090 And 1024 = 1024 Then MsgBox "desk"


ect well you get the idea

This works because you are doing a bitwise comparison.

So 1090 in binary is 10001000010

so when you do 2 and 1090 you are actually doing

10001000010
00000000010
-----------------
00000000010 = 2 decimal

1090 and 1024:

10001000010
10000000000
-----------------
10000000000 = 1024 decimal

[HarryW]

This is all much simpler in C you know. Anyway here's the loop that converts to binary Guv was talking about:

Dim BinaryArray(32) As Integer
Dim BitPos As Integer, FlagVariableCopy As Integer
FlagVariableCopy = FlagVariable 'FlagVariable is the variable containing your flagged bits
For BitPos = 0 To 31
    BinaryArray(BitPos) = FlagVariableCopy Mod 2
    FlagVariable = (FlagVariableCopy - 1) \ 2
Next BitPos

After this loop has run, BinaryArray should contain a 0 or a 1 in each element, corresponding to each bit in FlagVariable. FlagVariable is the variable in which your 'compound enumeration' is stored.

[paulw]

Would this be faster?

Dim BinaryArray(32) As Integer
Dim BitPos As Integer
For BitPos = 0 To 31    
  BinaryArray(BitPos) = FlagVariable And (2^BitPos)
Next BitPos

Cheers,

P.

[kedaman]

definitely not. And i wouldn't recommend convertion to binary, go with bitwise comparation

[HarryW]

The VB ^ power operator isn't that fast, so it's gonna be slower. Bitwise compares will be faster as Kedaman said, but it's kind of boring to code

[kedaman]

I disagree, if you're going to call convert to binary and optionally store the binary array to at least save some performance you're going to waste both time on coding as well as runtime performance.
If it helps, in case you haven't memorated the powers of 2 in decimal upto 2^32 as me, you can use hexadecimal expression format in vb:

Hex in vb, decimal, binary
&H1,  1,  1
&H2,  2,  10
&H4,  4,  100
&H8,  8,  1000
&H10, 16, 1 0000
&H20,  32, 10 0000
&H40,  64, 100 0000
&H80,  128, 1000 0000
&H100, 256, 1 0000 0000

...
&H80000000, 2 147 483 648,  1000 0000 0000 0000 0000 0000 0000 0000

[HarryW]

That's boring! Writing out powers of 2 isn't my idea of entertaining code

[kedaman]

thats my fun

[DavidHooper]

Yeh but guys, this powers-of-2 system has its limitations. Suppose I want to buy 2 chairs - how will you know whether I have bought 2 chairs or 1 couch?

Can you guys provide an alternative solution, which can efficiently tell how many chairs, couches etc I have bought?

I'll post my solution this afternoon (gmt).

[kedaman]

how many of each max? That would determine the radix, a power of 2 would be best

[DavidHooper]

Not a chance keda, we want unlimited numbers of any product.

Feel free to post partially working solutions though - praps 10 max for a prototype keda?

[kedaman]

unlimited numbers of any product - no solution
in vb there's restrictions but here's some good solutions
2147483647 - an array of longs
327687 - an array of integers
255 - an array of bytes
15 - an array of bytes a(x\2)\16 for hi nibble, a(x\2) and 15 for low nibble, the latter for odd the earlier for even x (index)

[DavidHooper]

Thats not a solution. A solution would be:

1) Here is some sort of numbering system.
2) If you give me a number, such as 1098, this is how i can tell you what furniture you purchased.
3) Some more mathematical explanation.

[kedaman]

an array would express a number, usefull as the amount of furniture types and max amount of each will raise the data length linearily. Now in case you want to use say Decimal datatype you have 96 bits to spend that would be 9 bits per furniture type for 10 furniture types giving a max of 2^9=512, but decimals are extreemly slow, a regular long would let you have 8 max per furniture type

[DavidHooper]

keda u are never clear enough for us... but i would like ure <clear> comment on my method!

The key here is to use multiplication, not addition.
OK, here goes. My method works by using prime numbers. Take an aMain(x) where x is the number of different items of furniture to be sold. Fill each element with consecutive prime numbers.
aMain(0)=2
aMain(1)=3
aMain(2)=5
aMain(3)=7
...etc...

Each element corresponds to an item of furniture. So aMain(0) means 'chair'. aMain(1) means 'table' etc. aMain(2) means 'stool'. aMain(3) means 'sofa'. Use an array to relate these if u want.

OK, so then u need something to record the order. Dim dblOrder as Double (needs to be big as primes rise... !). Put dblOrder=1.

Then if u order a chair: dblOrder=dblOrder * aMain(0).
If u order a table: dblOrder=dblOrder * aMain(1).
Table & chair: dblOrder=dblOrder * aMain(0) * aMain(1).

And so u get a code. Use the Mod operator to reverse this code in the items of furnitue. This code works with ordering two chairs etc and is, in fact, part of the design of my Anagram Ferret <see homepage, new version shortly>. And to top it off, it's more effecient than the powers of two stuff.

So, let me test you. The code is 3675. What did I order?

[kedaman]

No it's not efficient, maybe intuitive but not efficient. The user could order a high amount of chairs but only o couple of desks, the proportionality is not uniform. Not only the multiplication but even more the retrieval of the used primes will be very inefficient.
mod alone won't reverse the process, you need to test each type even for partial retrieval

The bits per furtniture type will have a uniform (therefore more memory efficient)proportions of the data and, and the algoritm will do addition (for incremention) or multiplication (for several) and bitwise and + integerdivision for retrieval.

[chrisf]

England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1

Originally posted by DavidHooper

Then if u order a chair: dblOrder=dblOrder * aMain(0).
If u order a table: dblOrder=dblOrder * aMain(1).
Table & chair: dblOrder=dblOrder * aMain(0) * aMain(1).

If I order 3 chairs:

3 * 2 = 6

but if I order 2 tables instead:

2 * 3 = 6

????????????????????????????

England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1

[kedaman]

Originally posted by chrisf
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1



If I order 3 chairs:

3 * 2 = 6

but if I order 2 tables instead:

2 * 3 = 6

????????????????????????????

England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1

3 ^ 2 = 9

2 ^ 3 = 8

[Guv]

In 1955 or there abouts, you had to worry a lot about how much time and what resources a program used.

Today the efficiency of the prime number approach should not be a problem.

The problem would be an order that resulted in a product greater than about 15 decimal digits. That is about the limit of the precison with which you can store and retrieve integers using a Double.

[kedaman]

Why not pick the obviously most simple solution?

[chrisf]

Originally posted by kedaman

3 ^ 2 = 9

2 ^ 3 = 8

O.K. then

1 of aMain(4) = 11^1 = 11

or

2 of aMain(1) and 1 of aMain(2) = 3^2 + 2^1 = 11


England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1

[kedaman]

Originally posted by chrisf


O.K. then

1 of aMain(4) = 11^1 = 11

or

2 of aMain(1) and 1 of aMain(2) = 3^2 + 2^1 = 11


England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1
England 5 - Germany 1

3^2 * 2^1 = 18

[chrisf]

I should stick to watching football.

[5speed]

It doesn't seem that it could work with the info given.
You have a number that is divisible by two, each product is divisible by two. unlimited possibilites and it does not have a great solution. If you had a number specific for two selections of furniture, or three. ie 1090 has to be three selections. then its plauseable, else I don't see how. what I understand is that there is unlimited number of funiture that number could have. So I think there is no real solution, since they would contradict themselves.

[aknisely]

Well, the example doesn't really fit. I'm using this method to store a configuration of options in a database, intead of having a boolean field for each option (there are about forty and grow every day). Since you can only have one choice for the option, then the quantity thereof is irrelevant.

[5speed]

ok so you can only have one chair, one sofa etc. That makes sense. That also akes it alot more easier

[DavidHooper]

Oh come on keda, give credit where it's due - it was a novel approach. I like it, I use it and I think it's useful and Guv obviously likes it aswell.

If u want to actually code your solution then I am more than happy to put them to the test for speed <challenge>.

In the meantime, I will have another look at this:

an array would express a number, usefull as the amount of furniture types and max amount of each will raise the data length linearily. Now in case you want to use say Decimal datatype you have 96 bits to spend that would be 9 bits per furniture type for 10 furniture types giving a max of 2^9=512, but decimals are extreemly slow, a regular long would let you have 8 max per furniture type

since you never posted a solution like I asked.

[kedaman]

Yes I would agree it is a novel approach, but it doesn't beat the classic one. I accept the challenge although I know the result already, do you use C++ or VB?

If the solution still is got unclear, it is based on data allocated per furniture, in bits, bytes if you want to be more performance efficient, strict hardware independent amount of combinations the data can express if memory efficiency is asked. I can't take credit for my solution, it's been used since the birth of computers and electronics

[DavidHooper]

Go for VB. These are the rules:

1) There are ten pieces of furniture. Chair, table, stool, cupboard, wardrobe, drawer, desk, sofa, rocking chair, shelves.
2) An random selection of ten pieces of furniture is taken. (duplicates allowed)
3) The code must generate a number for this order.
4) and then reverse the number to produce a string with the furnitue ordered.
5) this process will be timed.

accept? or modifications to the rules?

/dh/

[kedaman]

What will the maximum allowed amount per piece of furniture be? I would suggest 15 or 255
Will the challenge be concentrated on memory or performance efficiency or both?

[DavidHooper]

Rule 2 says:
2) An random selection of ten pieces of furniture is taken. (duplicates allowed)

Therefore the maximum possible of one type of furnitue is 10.

The challenge will focus on speed. Shortest time wins.

[kedaman]

Alright then, accepted

[kedaman]

One more thing, only 3) and 4) will be timed, while the order generation won't be timed, ok?

[DavidHooper]

ok. that is fair.

[aknisely]

[DavidHooper]

Sub Main()
Dim lngTimer As Long
Dim dblCode As Double
Dim aFurniture(9) As String
Dim aPrimes(9) As Integer
Dim strResult As String
Dim x As Integer
Dim y As Integer
'Set up variables
aPrimes(0) = 2
aPrimes(1) = 3
aPrimes(2) = 5
aPrimes(3) = 7
aPrimes(4) = 11
aPrimes(5) = 13
aPrimes(6) = 17
aPrimes(7) = 19
aPrimes(8) = 23
aPrimes(9) = 29
aFurniture(0) = "Table" & vbCrLf
aFurniture(1) = "Chair" & vbCrLf
aFurniture(2) = "Stool" & vbCrLf
aFurniture(3) = "Cupboard" & vbCrLf
aFurniture(4) = "Wardrobe" & vbCrLf
aFurniture(5) = "Rocking Chair" & vbCrLf
aFurniture(6) = "A" & vbCrLf
aFurniture(7) = "B" & vbCrLf
aFurniture(8) = "C" & vbCrLf
aFurniture(9) = "D" & vbCrLf
dblCode = 1

'Choose 10 random items of furniture and generate code
Randomize
For x = 0 To 9
dblCode = dblCode * aPrimes(Int(10 * Rnd))
Next x

'Start timer
lngTimer = Timer

'Deconstruct dblCode
For y = 0 To 9
For x = 0 To 9
If dblCode / aPrimes(x) = Int(dblCode / aPrimes(x)) Then
dblCode = dblCode / aPrimes(x)
strResult = strResult & aFurniture(x)
End If
Next x
Next y

MsgBox "The furniture order was:" & vbCrLf & strResult & vbCrLf & "Time elapsed: " & Timer - lngTimer
End Sub



I knocked this together in 15 minutes with little thought so excuse the lack of optimisation etc...

Now, for testing I used the oldest machine I could lay my hands on - a 486 33MHz processor. This is as slow as they come. Running the program a few times shows that this method is so fast (even on 33MHz!) that time elapsed is very close to 0. We know the Timer function is not all that accurate (and I can't be bothered to stick in TickCount) so I modified the program to deconstruct the furniture code 10000 times.

10000 deconstructions takes 11.1 seconds. Meaning each deconstruction takes on average just over one-thousandth of a second. Remember this is on a serious relic of a machine. OK, so I appreciate the elapsed time might be smaller if the random selection chooses, say, ten chairs rather than drawers (due to smaller integers) but you get the idea. Maximum time I saw was 11.5 seconds.

The prime number method works. The prime number method is fast. keds, you're welcome to d/l and test this code. Stick it in a module and compile away.

And this method could probably be improved so if you guys have any ideas...

Where's your offering keds?

[kedaman]

Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (Destination As Any, Source As Any, ByVal Length As Long)
Declare Sub ZeroMemory Lib "kernel32" Alias "RtlZeroMemory" (pDest As Any, ByVal cbZero As Long)

Private Declare Function QueryPerformanceCounter Lib "kernel32" (lpPerformanceCount As Currency) As Long
Private Declare Function QueryPerformanceFrequency Lib "kernel32" (lpFrequency As Currency) As Long

Sub eMain()
    Dim number@, pieces&(9), a(9) As Byte, b(7) As Byte
    Dim n&, s&
    Dim start@, finish@, freq@, total& 'QPC
    
    Randomize 'generating order
    For n = 0 To 9
        pieces(n) = Int(Rnd * 10)
    Next n
    ZeroMemory b(0), 8
    For n = 0 To 9
        a(pieces(n)) = a(pieces(n)) + 1
    Next n
    
    QueryPerformanceCounter start
    For n = 1 To 1000000
      
        b(0) = a(0) Or a(1) * 16& 'store order in number
        b(1) = a(2) Or a(3) * 16&
        b(2) = a(4) Or a(5) * 16&
        b(3) = a(6) Or a(7) * 16&
        b(4) = a(8) Or a(9) * 16&
        CopyMemory number, b(0), 5&
        CopyMemory b(0), number, 5& 'retrieving order from number
        a(0) = b(0) And 15&
        a(1) = b(0) \ 16&
        a(2) = b(1) And 15&
        a(3) = b(1) \ 16&
        a(4) = b(2) And 15&
        a(5) = b(2) \ 16&
        a(6) = b(3) And 15&
        a(7) = b(3) \ 16&
        a(8) = b(4) And 15&
        a(9) = b(4) \ 16&
    Next n
    QueryPerformanceCounter finish
    QueryPerformanceFrequency freq
    
    total = Int(CDbl(finish - start) / CDbl(freq) * 1000)
    MsgBox total & " ns"

End Sub

My code looks like this. Runs about a 300-400 ns on my Athlon 600 (about 3000 times faster). However I have to recode your solution so that we can make a fair comparation, because yours definitely has tons of bottlenecks, namely string concentrations, and also only 4) was timed, not both 3 and 4 as agreed.

[DavidHooper]

sorry about not timing 3)
the string concatenation at the end is part of the agreement. see 4b)
comparation? u mean comparison


now lets take your lowest time.
Yours: 300 microseconds = 0.0003 seconds.
Mine: 0.001 seconds
Difference factor: 3.3x to you
CPU difference factor: 18x (3000x???)

I win.