Generate combinations from a given range

huangapple go评论78阅读模式
英文:

Generate combinations from a given range

问题

我正在尝试创建一个能够从给定范围生成组合的程序。

我开始编辑下面的代码来生成组合:

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

这是代码的输出:

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

这是我编辑过的代码:

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
    }
}

输出结果为:

BA
BB
BC
BD
BE
CA

我的代码是有效的,但是如果我增加组合的长度,并且我的范围从中间开始,程序将生成我不想要的组合(当然这将花费很长时间)。
我该如何解决这个问题?

英文:

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 &quot;fmt&quot;

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 &gt;= 0; i-- {
            x[i]++
            if x[i] &lt; len(r) {
                break
            }
            x[i] = 0
            if i &lt;= 0 {
                x = x[0:0]
                break
            }
        }
        return string(p)
    }
}

func main() {
    np := nextPassword(2, &quot;ABCDE&quot;)
    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 &quot;fmt&quot;

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 &gt;= 0; i-- {
            x[i]++
            if x[i] &lt; len(r) {
                break
            }
            x[i] = 0
            if i &lt;= 0 {
                x = x[0:0]
                break
            }
        }
        return string(p)
    }
}

func main() {
	cont := 0
    np := nextPassword(2, &quot;ABCDE&quot;)
    for {
        pwd := np()
        if len(pwd) == 0 {
            break
        }
		if cont &gt;= Min &amp;&amp; cont &lt;= Max{
			fmt.Println(pwd)
		} else if cont &gt; 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?

答案1

得分: 1

我真的不喜欢nextPassword的写法,所以我做了一些改动。与其从0开始并重复返回下一个值,这个函数接受一个整数并将其转换为相应的“密码”。例如,toPassword(0, 2, []rune("ABCDE"))的结果是AAtoPassword(5, ...)的结果是BA

从那里开始,你可以轻松地循环遍历任何你想要的范围。但我还写了一个nextPassword的包装函数,它的行为类似于原始代码中的那个。这个函数在内部使用toPassword,并接受一个起始值n

可运行版本在这里:https://play.golang.org/p/fBo6mx4Mji

以下是代码:

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
}
英文:

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(&quot;ABCDE&quot;)) 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 (
&quot;fmt&quot;
)
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 &quot;ABCDE&quot;)
for n &gt; 0 {
// Filling from the right, put the right digit mod b
result[i] = alphabet[n%base]
// Divide the number by the base so we&#39;re ready for
// the next digit
n /= base
// Move to the left
i -= 1
}
// Fill anything that&#39;s left with &quot;zeros&quot; (first letter of
// the alphabet)
for i &gt;= 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 &lt; 11; i++ {
fmt.Println(toPassword(i, 2, []rune(&quot;ABCDE&quot;)))
} // BA, BB, BC, BD, BE, CA
// Now do the same thing using nextPassword
np := nextPassword(5, 2, []rune(&quot;ABCDE&quot;))
for i := 0; i &lt; 6; i++ {
fmt.Println(np())
} // BA, BB, BC, BD, BE, CA
}

huangapple
  • 本文由 发表于 2017年7月1日 03:43:37
  • 转载请务必保留本文链接:https://go.coder-hub.com/44853839.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定