Number combinations [Solved]

[bogs]

Ok, I thought I would be able to figure this out on my own, but I must be missing something very simple.

What I am attempting to solve is listing every combination from 0 to 1 for x number of digits.

What I wrote works if there are only 2 digits, or up to a certain point if there are any more than that, but of course the end is still goofed up and filled with a number of duplicate entries proportional to the number of digits.

Stuttering stack...

cTesterDupes.png (48.37 KiB) Viewed 6576 times

...no dupe here...

cTesterDupless.png (34.84 KiB) Viewed 6576 times

I wound up cheating to solve this by throwing the list into an array then recombining it into a list, but what I really want to know is what did I do wrong that I am missing?

nineCount.livecode.zip

(1.52 KiB) Downloaded 169 times

[[-hh]]

Code: Select all

-- returns the 2^n possible n-bit nums (base 2),
--         that is 2^n lines of n chars each.
-- usage: put nBits(n,0&cr&1) into theBits
function nBits n,t 
  if n=1 then return t
  repeat for each line L in t
    put cr & L & "0" after s
    put cr & L & "1" after s
  end repeat
  return nBits(n-1,char 2 to -1 of s)
end nBits

on mouseUp
  put the millisecs into m1
  set cursor to watch; lock messages; lock screen
  put 3 into N -- the num of bits from a field or a scrollbar
    put nBits(N,0&cr&1) into theBits
  put the millisecs-m1 & " ms" into fld "timing"
  -- takes a lot of time, use file instead of a fld
  -- to write the 2^N lines of N chars each for N > 15:
  put theBits into fld "out"
end mouseUp

For small N you could also use baseConvert, but compare the timing.
I looked into your approach, I can't see any advantage of using arrays here (it is creating new order of elements and by that creating problems for you).

p.s. 2^3 is not nine (your stackname)

[[-hh]]

This is LiveCode at its best.
The following script creates all 24-bit nums to base 2 in lines = 25*2^24-1 = 419,430,399 Bytes (419,4 MByte) and writes them to a text file in < 40 seconds (total) on a medium fast machine.

Code: Select all

on mouseUp
  put the millisecs into m1
  set cursor to watch; lock messages; lock screen
  put 24 into n --> 24*2^24 + 2^24-1 =  419430399 Bytes
  put nBits(n,0&cr&1) into theBits 
  put bitfilename(n) into f
  put theBits into url("file:"&f)
  put "(n+1)*2^n-1="&(n+1)*2^n-1&": "&the millisecs-m1& \
      " ms" into fld "timing"
end mouseUp

function nBits n,t -- returns the 2^n possible n-bit nums
  if n=1 then return t
  repeat for each line L in t
    put cr & L & "0" after s
    put cr & L & "1" after s
  end repeat
  return nBits(n-1,char 2 to -1 of s)
end nBits

function bitfileName n
  put the effective filename of this stack into f
  set itemdel to slash
  put "bits"&format("%02d.text",n) into last item of f
  return f
end bitfileName

LC 8.1.10 is 15% faster with that than 9.0.5 and 9.0.5 is 10% faster with that than 9.5.0 ... (MacOS Catalina, Mac Mini 2.5GHz)

[bogs]

Heh, thanks Hermann, I was sure there was an easier way to do it than I had picked, since I made mine up out of my head and am not a math type

I also knew I didn't explain nearly clearly enough the goals and parameters, but I only had a brief amount of time.

p.s. 2^3 is not nine (your stackname)

The stack was named for my original goal as the maximum number of digits it would solve for, 9 was going to be the limit. As I was testing the solution I wrote, though, I wanted to see how far it would solve for. I locked it at 20 now, but during the testing I went as high as 50. The solution I wrote seems to work through all the combo's I tested.

Speed also wasn't an issue, nor was it a consideration for this. I just wanted to see if I could write a solution that would work with what I know, the approach I took was replacing a character under x condition. you might notice if you comment the array out that the digits do not run consecutively down the list, i.e.

Code: Select all

000
001 <-- 1st 1 starts far right
010 <-- 1st 1 moves to middle
100 <-- 1st 1 arrives at end left
101 <-- 2nd 1 starts far right
110 <-- 2nd 1 moves to middle, can not move farther
111 <-- 3rd 1 starts and stops, no further moves

which is the pattern I was shooting for and had gotten before having to remove duplicates which is why I used the array then broke it up again, not for speed. Heck, I even had a wait introduced in my own code so I could see each number get entered and watch the pattern.

The pattern is also what prompted the question, even sorted the array method winds up resolving to the pattern your approaches use.

What I really want to know is, why didn't that original approach work?

Your approach is far better for solving the problem, i.e. finding out how many combinations there are, but shouldn't a purely character based approach that leaves the pattern described above work as well? I am sure there is a method, just like I'm sure I'm missing it, I'm just curious what it is.

Lastly, just to show how ignorant I am about math, I used baseConvert in that color tutorial I did, how would that apply here? I couldn't see a pattern I could use with it myself, nor could I find a way to do this in a spreadsheet program. I'm not saying there isn't one, just that it is beyond MY limitations in that type of program heh.

[SparkOut]

In your "What it should look like" image there is no pattern for "011" - is this intentional?

I am not sure if this is where you are going, but I imagine Hermann believes it to be the case too, that you are finding the unique patterns of 1 or 0 possible for a given length of string. This is essentially binary representation. For a string of length 8, you get a range that can be rendered in base 2 from 0 to 255. So there's where the baseConvert function could be applied. Hermann has done the job of making it possible to have many more digits without melting brains, and with a more efficient method than using the baseConvert function.

If that is not pertinent to your question, then I am not understanding what you are trying to get. I didn't get my head around your original approach either, so can't suggest why that might not behave as you wished. My head just took the easy way and just followed Hermann's route.

[bogs]

In your "What it should look like" image there is no pattern for "011" - is this intentional?

Well, it is as the problem I'm trying to solve was explained to me, which is what I put in the code block in the previous post.

Problem explanation as I received it was:
you have x amount of 0s, lets say 5 -> 00000
you put a "1" into the first digit of 5 -> 00001
you move the 1 to the left by 1 character each
line until there are no more moves. -> 00010 <-
when it reaches the end, the first block
ends, and you start the next block -> 10000 <- ends first block, next block starts with 10001

Hope that helps to clarify it a bit.

Hermann's solution solves for *all* possible combinations, but that isn't the goal for this problem as I understood it. Thanks for the explanation on the baseConvert, now I get that suggestion too

Like I said, to me, it seems like it should be a simple character position move problem and that is how I approached it.

I'll ask the guy that posed the problem to me for clarification when I'm in class today

[[-hh]]

What I am attempting to solve is listing every combination from 0 to 1 for x number of digits

So your example for x=3 misses 011 as SparkOut wrote.
You are listing (in base 10) 0,1,2,4,5,6,7. This is not 'every combination'.

Let us now look at the (incomplete) pattern you try to achieve:

x=1: 0,1 (2)
x=2: 00,01,10,11 (4)
x=3: 000,001,010,100,101,110,111 (7)
x=4: 0000,0001,0010,0100,1000,1001,1010,1100,1101,1110,1111 (11)

Starting with x=2 you effectively do the following for any fixed integer x > 2:
Take the first x 'numbers' of the (x-1)-List and prepend zero to each 'number'. Then take the full (x-1)-List and prepend one to each 'number'.

It is easy to see (by mathematical induction) that this leads to:

The number of 'numbers'/lines is  x*(x+1)/2 + 1  for your x-digit pattern.

[So, for x=25 you have 25*13+1 = 326 'numbers'/lines]

Now the following function does this recursively to get for a given x all x*(x+1)/2 + 1 'numbers' according to your pattern.

Code: Select all

-- usage: put 50 into N
-- put bogspattern(1,N,0&cr&1) into fld "out"
function bogspattern m,N,t
   if m=N then return t
   repeat with j=1 to m+1
     put cr & "0" & line j of t after s
   end repeat
   repeat for each line L in t
     put cr & "1" & L after s
   end repeat
   return bogspattern(m+1,N,char 2 to -1 of s)
end bogspattern

[Thierry]

Hi Bogs,

my take on this.

Code: Select all

on printallStringsFrom s, k
   put empty into fld "list"
   printStrings s, "", the number of chars of s , k
end printallStringsFrom

on printStrings s, prefix, n, k
   if k = 0 then
      put prefix &cr after fld "list"
   else      
      repeat with i = 1 to n step 1
         printStrings s, prefix & char i of s, n, k - 1
      end repeat
   end if
end printStrings

and you call it this way:

Code: Select all

on mouseUp
   put 3 into stringLength
   printallStringsFrom "01", stringLength
end mouseUp

Is this what you are looking for?

of course, you can call this function in different ways:

Code: Select all

   printallStringsFrom "AB", 1
   printallStringsFrom "ABCD", 1
   printallStringsFrom "ABCD", 4
   ....
   

Regards,

Thierry

[dunbarx]

Bogs.

I have glanced at the scripts given by others. But doesn't this do what you want:

Code: Select all

on mouseUp
   put the ticks into g
   put "000000000000" into zeros
   repeat with y = 1 to 8192
      put baseConvert(y,10,2) into line y of temp
   end repeat
   repeat for each line tLine in temp
      put zeros before tline
      delete char 1 to -14 of tLine
      put tLine & return after accum
   end repeat
   delete the last line of accum
   answer the ticks - g
end mouseUp

I saw comments about using baseConvert. Is it just the time it takes if the maximum value is much higher than the 16384 above (about 1 second)?

Craig

[bogs]

The very first thing I want to say is THANK YOU ALL

When I got to class, I brought up what SparkOut pointed out to the guy that posed the problem to me initially, and I explained to him that the code that does what he wants wouldn't give him every possible combination, which way did he want it?

Turns out he wanted it both ways, but every possible combination was the more important of the two heh. Me, I feel like I was lead down a rabbit hole, but it isn't the first time I've felt that way, and probably won't be the last.

Sorry for dragging you all down it with me

@Hermann - Thank you for that explanation, it makes a lot more sense to me now, though I'm not sure you should have named a function after me as it might be too much honor

Kidding aside, all of the functions you provided were not only educational, but solved the problem in fewer lines that I was able to do it in.

@ Thierry - nice, simple, and to the point for getting all combinations in a way I could understand.

@ Craig - the time mattered not at all to me, as I said, the original stack I posted had a 'wait' command in it which I varied from 1 tick to 2 seconds while writing out the code to slow it down on purpose. The code was an interesting take on it to me as well, I know I never would have thought of it.

[rkriesel]

Bogs: Even though you don't care about speed for this app, perhaps much faster code would be interesting or illuminating.

Some feel the need for speed. Hermann's nBits presents a good opportunity for eliminating a "repeat for each line" statement.

Here's a version that produces the same output as nBits, but does it about eight times as fast on my machine.

Code: Select all

function nBits n,t -- returns the 2^n possible n-bit nums -- from Hermann
   local s
   if n=1 then return t
   repeat for each line L in t
      put cr & L & "0" after s
      put cr & L & "1" after s
   end repeat
   return nBits(n-1,char 2 to -1 of s)
end nBits

function nBits2 pLength -- advantages: no "repeat for each line" and no recursion
   local tStrings
   put cr & "0" & cr & "1" into tStrings
   repeat with i = 2 to pLength
      replace cr with cr & 0 in tStrings -- put 0 before each line
      get tStrings
      replace cr & 0 with cr & 1 in it -- replace each leading 0 with 1
      put it after tStrings
   end repeat
   delete char 1 of tStrings
   return tStrings
end nBits2

on mouseUp
   set cursor to watch
   local tMilliseconds, tStrings, tReport
   repeat with tLength = 2 to 24
      put - the milliseconds into tMilliseconds[ "nBits" ]
      put nBits( tLength, "0" & cr & "1" ) into tStrings[ "nBits" ]
      add the milliseconds to tMilliseconds[ "nBits" ]
      
      put - the milliseconds into tMilliseconds[ "nBits2" ]
      put nBits2( tLength ) into tStrings[ "nBits2" ]
      add the milliseconds to tMilliseconds[ "nBits2" ]
      
      if tMilliseconds[ "nBits" ] > 5 and tMilliseconds[ "nBits2" ] > 0 then
         get tLength \
               && ( number of lines in tStrings[ "nBits" ] ) \
               && ( tStrings[ "nBits" ] = tStrings[ "nBits2" ] ) \
               && tMilliseconds[ "nBits" ] \
               && tMilliseconds[ "nBits2" ] \
               && round( ( tMilliseconds[ "nBits2" ] - tMilliseconds[ "nBits" ] ) * 100 / tMilliseconds[ "nBits" ] ) & "%" \
               & cr
         put it after msg
         put it after tReport
         wait 0 with messages
      end if
   end repeat
   if tReport is not empty then
      replace space with comma in tReport
      put "length,count,nBits=nBits2,nBits ms,nBits2 ms,delta" & cr before tReport
   end if
   breakpoint
end mouseUp

Here's the report on my 2017 iMac 3.8GHz with LC Indy 9.5.0.

Code: Select all

length,count,nBits=nBits2,nBits ms,nBits2 ms,delta
11,2048,true,7,1,-86%
12,4096,true,16,1,-94%
13,8192,true,31,2,-94%
14,16384,true,61,7,-89%
15,32768,true,141,10,-93%
16,65536,true,276,19,-93%
17,131072,true,590,48,-92%
18,262144,true,1192,122,-90%
19,524288,true,1679,161,-90%
20,1048576,true,3872,534,-86%
21,2097152,true,7767,1060,-86%
22,4194304,true,15950,1563,-90%
23,8388608,true,31288,4428,-86%
24,16777216,true,63586,7792,-88%

Thanks, all, for the discussion.
-- Dick

[bogs]

Bogs: Even though you don't care about speed for this app, perhaps much faster code would be interesting or illuminating.

That is true, and I find all the ways to solve something to be one or the other or both. I just wanted to make sure due to the number of times I saw speed testing as part of the answer that it was known that wasn't the primary motivation here.

My solution, by far the slowest of the group, did solve what was explained to me as the original problem, I just didn't (and still don't) know why it produced duplicate results towards the end. Of course, neither the person that explained the problem originally nor myself caught on that for every combination produced by that method, once finished, would have to have the result mirrored and flipped (i.e., I solved half the problem, mirroring it would solve the other half).

Once SparkOut pointed it out to me (thanks for that!) and I passed it down the line, well, we wound up here. Even though the problem is 'solved', I'd still like the other answer I was looking for, i.e. how duplicate entries wound up in my list from my original code before I threw everything into array keys and split it back.

I understand why doing the combine and split works, that I don't need explained, but comment that section out and run say, 3 (or more) numbers in the original stack.

[[-hh]]

@Dick.

This is a clever and wonderful idea to use replace for the "block prepending" another digit.
But "no recursion" isn't necessarily an advantage (as you wrote). For example, putting your idea into a recursive function will not loose in speed against your repeat variant:

Code: Select all

-- usage: put nBits3(n,cr) into theBits 
-- n is the num of digits
function nBits3 n,t0 -- recursion variant
  put t0 into t1
  replace cr with cr&0 in t0
  replace cr with cr&1 in t1
  if n > 1 then return nBits3(n-1,t0&t1)
  else return char 2 to -1 of t0&t1
end nBits3

Here is your repeat variant in a slightly modified form that will probably win this speed contest (for large n) by a hair's breadth:

Code: Select all

-- usage: put nBits2a(n) into theBits 
-- n is the num of digits
function nBits2a pLength -- repeat variant
  local tStrings, tStringx
  put cr & "0" & cr & "1" into tStrings
  repeat pLength-1
    put tStrings into tStringx
    replace cr with cr & "0" in tStrings
    replace cr with cr & "1" in tStringx
    put tStringx after tStrings
  end repeat
  return char 2 to -1 of tStrings
end nBits2a

[bogs]

Just replying to point out that this last reply is from a bot, it quoted a part of an earlier reply I myself made...

When I got to class, I brought up what SparkOut pointed out to the guy that posed the problem to me initially, and I explained to him that the code that does what he wants wouldn't give him every possible combination, which way did he want it?

Who ever wants to delete it may feel free to delete this post pointing it out