Re: [go-nuts] Generation of Strings - generation

2016-07-15 Thread Michael Jones 
Whatever they wanted, we've put far more into answering it than than they
have in responding. I sent my response taking time from the Farnborough Air
Show, not wanting their concerns to go unaddressed. Disappointed to see no
following reply to all the good advice from everyone here.
On Jul 15, 2016 6:25 PM, "'Paul Borman' via golang-nuts" <
golang-nuts@googlegroups.com> wrote:

> It wasn't clear to me what the OP wanted.  Did they just want to print
> them?  Did they want to use them?  For use, I think the channel is probably
> the most straightforward to use, but the OP didn't want any channels at
> all.  The underlying array that slices refer to could also be made smaller,
> for example, set = "ab" and size = 3 can be satisfied with the underlying
> text of aaababbbaa.  I didn't bother to try and figure out a general
> algorithm, however, I just did that one by hand.
>
> -Paul
>
> On Fri, Jul 15, 2016 at 10:07 AM, Bakul Shah  wrote:
>
>> Ah. Should've read your original play link more carefully!
>> You could've made it a bit more efficient by allocating one
>> large string (N^N+N) and one Printf! Of course, that'd fall
>> apart once you have more combinations than can fit in memory
>> but that is easily solved.
>>
>> Still interested in knowing if anyone has an more efficient
>> greycode sequence algorithm.
>>
>> On Fri, 15 Jul 2016 09:56:55 PDT Paul Borman  wrote:
>> >
>> > BTW, the solution I provided does change one digit at a time, working
>> just
>> > like an odometer.  The OP privately said that even the reporting channel
>> > was undesired in my solution, so I sent the OP a link to one that
>> allocated
>> > a slice and then filled it in, rather than sending it down a channel.
>> The
>> > OP never responded after I sent a link to the second version (
>> > https://play.golang.org/p/bL9g8CM4DC) , so I guess it addressed the
>> OP's
>> > issue, or the OP found a different solution.
>> >
>> > On Thu, Jul 14, 2016 at 11:10 PM, Bakul Shah 
>> wrote:
>> >
>> > > What the OP wants is equivalent to generating *all* n digit numbers in
>> > > base n. For example, given
>> > >
>> > > aa
>> > > ab
>> > > ba
>> > > bb
>> > >
>> > > if you map a to 0 and b to 1 you get numbers 0..3 (base 2). In general
>> > > you have n^n combinations..
>> > >
>> > > If you consider only the cost of *copying* (or changing an existing
>> strin=
>> > g
>> > > to a different one), it is clear the least cost can be obtained by
>> changi=
>> > ng
>> > > 1 digit at a time to go to the next combination (using base N
>> greycoding =
>> > -
>> > > if there is such a thing). So for example, for abc, you=E2=80=99d do
>> some=
>> > thing like
>> > >
>> > > aaa
>> > > aab
>> > > aac
>> > > bac
>> > > bab
>> > > baa
>> > > caa
>> > > cab
>> > > cac
>> > >
>> > > and so on. Then the total cost is n^n-1 digit changes. Though I do not
>> > > know of an efficient base N greycoding algorithm.
>> > >
>> > > ON the other hand a traditional counter (as below) won=E2=80=99t be
>> signi=
>> > ficantly
>> > > more expensive.
>> > >
>> > > var dig [n]int
>> > > outer:
>> > > for {
>> > > for j =3D n-1; j >=3D 0; j=E2=80=94 {
>> > > ++dig[j]
>> > > if dig[j] < n { /* output and */ continue outer }
>> > > dig[j] =3D 0
>> > > }
>> > > if j =3D=3D -1 { break }
>> > > }
>> > >
>> > > On Jul 13, 2016, at 11:17 PM, Michael Jones 
>> > > wrote:
>> > >
>> > > The first time this came up I wrote code to generate general alphabet
>> > > combinations as quickly as I could. The approach I used was a
>> generator
>> > > object that one calls to set the length and alphabet size, and a
>> Next()
>> > > function that is called repeatedly until it signals that all values
>> have
>> > > been generated. The values are handled in a slightly indirect way.
>> > >
>> > > There are three use modes:
>> > > (a) Simply advance the internal state by calling Next() until
>> done,
>> > > this lets you count the number of solutions without looking at the
>> detail=
>> > s,
>> > > as in some of the associated tests.
>> > > (b) Interpret the present state as an array of symbols from the
>> > > user-supplied alphabet string in a reused array. In this case, there
>> is n=
>> > o
>> > > allocation or garbage during generation.
>> > > (c) Interpret the present state as a string, such simply creates a
>> > > string. This is (b) plus string creation and GC overhead. It is about
>> 2.6
>> > > to 3.1 times slower.
>> > >
>> > > There are two modes of generation as well, ordered (=E2=80=9CAA, AB,
>> BB=
>> > =E2=80=9D) and
>> > > unordered (=E2=80=9CAA, AB, BA, BB=E2=80=9D). From the original post
>> here=
>> > , clearly
>> > > unordered is the desired mode. The speeds of this on my MacBook feel
>> fast=
>> > =E2=80=A6
>> > >
>> > > BenchmarkUnordered1-828.21
>> > > ns/op
>> > > BenchmarkUnordered2-85000 32.3
>>

Re: [go-nuts] Generation of Strings - generation

2016-07-12 Thread 'Paul Borman' via golang-nuts 
Something like https://play.golang.org/p/dZjaaorPcb ?

On Tue, Jul 12, 2016 at 1:54 PM, The MrU  wrote:

> Hi,
>
> I have this code https://play.golang.org/p/9o5TReZ7jT3
> 
>
> My idea was to generate all possible combinations pretty much this:
>
> aaa
> bbb
> ccc
> abb
> acc
> baa
> bbb
> bcc
> caa
> cbb
> ccc
> aba
> abb
> abc
>
> you get the picture I think.
>
> I got this solution but the objective is to simplify the solution without
> using channels if possible :
>
> package main
>
> import "fmt"
>
> func GenerateCombinations(alphabet string, length int) <-chan string {
>   c := make(chan string)
>
>   go func(c chan string) {
>   defer close(c)
>
>   AddLetter(c, "", alphabet, length)
>   }(c)
>
>   return c
> }
>
> func AddLetter(c chan string, combo string, alphabet string, length int) {
>   if length <= 0 {
>   return
>   }
>
>   var newCombo string
>   for _, ch := range alphabet {
>   newCombo = combo + string(ch)
>   c <- newCombo
>   AddLetter(c, newCombo, alphabet, length-1)
>   }
> }
>
> func main() {
>
>   list := "abc"
>
>   for combination := range GenerateCombinations(list, 3) {
>   if len(combination) == 3 {
>   fmt.Println(combination)
>   }
>
>   }
>
>   fmt.Println("Done!")
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[go-nuts] Generation of Strings - generation

2016-07-12 Thread The MrU 


Hi,

I have this code https://play.golang.org/p/9o5TReZ7jT3 


My idea was to generate all possible combinations pretty much this:

aaa
bbb
ccc
abb
acc
baa
bbb
bcc
caa
cbb
ccc
aba
abb
abc

you get the picture I think.

I got this solution but the objective is to simplify the solution without 
using channels if possible :

package main

import "fmt"

func GenerateCombinations(alphabet string, length int) <-chan string {
c := make(chan string)

go func(c chan string) {
defer close(c)

AddLetter(c, "", alphabet, length)
}(c)

return c
}

func AddLetter(c chan string, combo string, alphabet string, length int) {
if length <= 0 {
return
}

var newCombo string
for _, ch := range alphabet {
newCombo = combo + string(ch)
c <- newCombo
AddLetter(c, newCombo, alphabet, length-1)
}
}

func main() {

list := "abc"

for combination := range GenerateCombinations(list, 3) {
if len(combination) == 3 {
fmt.Println(combination)
}

}

fmt.Println("Done!")
}

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.