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 string to a
different one), it is clear the least cost can be obtained by changing 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’d do something 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’t be significantly more
expensive.
var dig [n]int
outer:
for {
for j = n-1; j >= 0; j— {
++dig[j]
if dig[j] < n { /* output and */ continue outer }
dig[j] = 0
}
if j == -1 { break }
}
> On Jul 13, 2016, at 11:17 PM, Michael Jones <michael.jo...@gmail.com> 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 details, 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 no
> 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 (“AA, AB, BB”) and
> unordered (“AA, AB, BA, BB”). From the original post here, clearly unordered
> is the desired mode. The speeds of this on my MacBook feel fast…
>
> BenchmarkUnordered1-8 200000000 8.21 ns/op
> BenchmarkUnordered2-8 50000000 32.3 ns/op
> BenchmarkUnordered3-8 10000000 194 ns/op
> BenchmarkUnordered4-8 1000000 1538 ns/op
> BenchmarkUnordered5-8 100000 18404 ns/op
> BenchmarkUnordered6-8 5000 255203 ns/op
> BenchmarkUnordered7-8 300 4163767 ns/op
> BenchmarkUnordered8-8 20 81721059 ns/op
> BenchmarkUnordered9-8 1 1883039855 ns/op
>
> BenchmarkUnorderedRate1-8 500000000 3.68 ns/op
> BenchmarkUnorderedRate2-8 200000000 7.92 ns/op
> BenchmarkUnorderedRate3-8 100000000 13.4 ns/op
> BenchmarkUnorderedRate4-8 100000000 18.6 ns/op
> BenchmarkUnorderedRate5-8 100000000 24.1 ns/op
> BenchmarkUnorderedRate6-8 50000000 27.9 ns/op
> BenchmarkUnorderedRate7-8 50000000 32.2 ns/op
> BenchmarkUnorderedRate8-8 30000000 37.3 ns/op
> BenchmarkUnorderedRate9-8 30000000 40.7 ns/op
>
> …with speeds for s-symbol alphabets of lengths 1..s being low tens of
> nanoseconds per combination in array modes and ~3x that in string mode. This
> is no channel, no allocation or freeing, no GC needed, no recursion. Because
> it has tests and the code in separate files, it is not really a good go
> playground candidate. Sorry.
>
>
> From: <golang-nuts@googlegroups.com <mailto:golang-nuts@googlegroups.com>> on
> behalf of catalas...@gmail.com <mailto:catalas...@gmail.com>
>
> 2016년 7월 13일 수요일 오전 6시 36분 15초 UTC+9, The MrU 님의 말:
>> Hi,
>>
>> I have this code https://play.golang.org/p/9o5TReZ7jT3
>> <https://play.golang.org/p/9o5TReZ7jT>
>> 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
> <mailto:golang-nuts+unsubscr...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout
> <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
> <mailto:golang-nuts+unsubscr...@googlegroups.com>.
> For more options, visit https://groups.google.com/d/optout
> <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.
