Generation of Strings

The MrU

unread,

Jul 12, 2016, 5:36:15 PM7/12/16

to golang-nuts

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!")
}

Paul Borman

unread,

Jul 12, 2016, 6:26:51 PM7/12/16

to The MrU, golang-nuts

Something like https://play.golang.org/p/dZjaaorPcb ?

--
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...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

catal...@gmail.com

unread,

Jul 13, 2016, 11:12:29 AM7/13/16

to golang-nuts

what about https://play.golang.org/p/TbZ-fbhUCb ?

the code don't create goroutine. thus you don't have to care about troubles with managing goroutine.

2016년 7월 13일 수요일 오전 6시 36분 15초 UTC+9, The MrU 님의 말:

Michael Jones

unread,

Jul 14, 2016, 2:17:58 AM7/14/16

to catal...@gmail.com, golang-nuts

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.

--

Bakul Shah

unread,

Jul 15, 2016, 2:10:32 AM7/15/16

to golang-nuts

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 }