生成给定范围内的组合

Question

I'm trying to create a program capable to generate combinations from a given range.

I started editing this code below that generates combinations:

package main

import "fmt"

func nextPassword(n int, c string) func() string {
    r := []rune(c)
    p := make([]rune, n)
    x := make([]int, len(p))
    return func() string {
        p := p[:len(x)]
        for i, xi := range x {
            p[i] = r[xi]
        }
        for i := len(x) - 1; i >= 0; i-- {
            x[i]++
            if x[i] < len(r) {
                break
            }
            x[i] = 0
            if i <= 0 {
                x = x[0:0]
                break
            }
        }
        return string(p)
    }
}

func main() {
    np := nextPassword(2, "ABCDE")
    for {
        pwd := np()
        if len(pwd) == 0 {
            break
        }
        fmt.Println(pwd)
    }
}

This is the Output of the code:

AA
AB
AC
AD
AE
BA
BB
BC
BD
BE
CA
CB
CC
CD
CE
DA
DB
DC
DD
DE
EA
EB
EC
ED
EE

And this is the code I edited:

package main

import "fmt"

const (
    Min = 5
    Max = 10
)

func nextPassword(n int, c string) func() string {
    r := []rune(c)
    p := make([]rune, n)
    x := make([]int, len(p))
    return func() string {
        p := p[:len(x)]
        for i, xi := range x {
            p[i] = r[xi]
        }
        for i := len(x) - 1; i >= 0; i-- {
            x[i]++
            if x[i] < len(r) {
                break
            }
            x[i] = 0
            if i <= 0 {
                x = x[0:0]
                break
            }
        }
        return string(p)
    }
}

func main() {
    cont := 0
    np := nextPassword(2, "ABCDE")
    for {
        pwd := np()
        if len(pwd) == 0 {
            break
        }
        if cont >= Min && cont <= Max{
            fmt.Println(pwd)
        } else if cont > Max{
            break
        }
        cont += 1
    }
}

Output:

BA
BB
BC
BD
BE
CA

My code works, but if I increase the length of the combination and my range starts from the middle, the program will generate even the combinations that I don't want (and of course that will take a lot of time). How can I solve this problem?

Answer 1

I really didn't like how nextPassword was written, so I made a variation. Rather than starting at 0 and repeatedly returning the next value, this one takes an integer and converts it to the corresponding "password." E.g. toPassword(0, 2, []rune("ABCDE")) is AA, and toPassword(5, ...) is BA.

From there, it's easy to loop over whatever range you want. But I also wrote a nextPassword wrapper around it that behaves similarly to the one in the original code. This one uses toPassword under the cover and takes a starting n.

Runnable version here: https://play.golang.org/p/fBo6mx4Mji

Code below:

package main

import (
    "fmt"
)

func toPassword(n, length int, alphabet []rune) string {
    base := len(alphabet)

    // This will be our output
    result := make([]rune, length)

    // Start filling from the right
    i := length - 1

    // This is essentially a conversion to base-b, where b is
    // the number of possible letters (5 in the case of "ABCDE")
    for n > 0 {
        // Filling from the right, put the right digit mod b
        result[i] = alphabet[n%base]

        // Divide the number by the base so we're ready for
        // the next digit
        n /= base

        // Move to the left
        i -= 1
    }

    // Fill anything that's left with "zeros" (first letter of
    // the alphabet)
    for i >= 0 {
        result[i] = alphabet[0]
        i -= 1
    }

    return string(result)
}

// Convenience function that just returns successive values from
// toPassword starting at start
func nextPassword(start, length int, alphabet []rune) func() string {
    n := start
    return func() string {
        result := toPassword(n, length, alphabet)
        n += 1
        return result
    }
}

func main() {
    for i := 5; i < 11; i++ {
        fmt.Println(toPassword(i, 2, []rune("ABCDE")))
    } // BA, BB, BC, BD, BE, CA

    // Now do the same thing using nextPassword
    np := nextPassword(5, 2, []rune("ABCDE"))
    for i := 0; i < 6; i++ {
        fmt.Println(np())
    } // BA, BB, BC, BD, BE, CA
}