[算法] 列出 5 个开关的所有开关情况？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2027 天前的主题，其中的信息可能已经有所发展或是发生改变。

5 个开关相当于 5 个二进制位。

列出 5 个二进制位的所有排列情况。

类似：

0,0,0,0,0 ；

0,0,0,0,1 ；

0,0,0,1,0 ；

0,0,0,1,1 ；

0,0,1,0,0 ；

0,0,1,0,1 ；

······

第 1 条附言 · 2019-04-28 16:48:28 +08:00

发现一种方法，可以这么列。
但是有个问题，最后一个全是 1 的情况没有打印出来。

//列出所有情况
var recursion = function (arr, num) {
if (num < arr.length ) {
arr[num] = 0;
recursion (arr, num + 1);
console.log(arr.toString());
arr[num] = 1;
recursion (arr, num + 1);
}
}

第 2 条附言 · 2019-04-30 08:55:56 +08:00

确实用 1 楼回复的方法是最好的。

for i in range(2**5):
print bin(i)

用 2 的 n 次方次循环。但是这种方法，就体会不到，每个开关变换的情况。

转换成二进制，可以考虑用别的方法替换。

开关

二进制位

列出

算法

28 条回复

binux

2019-04-28 11:30:20 +08:00

for i in range(2**5):
print bin(i)

YYSWDD

2019-04-28 11:36:49 +08:00

@binux #1 用算法实现。循环，递归把这个列出来。。

binux

2019-04-28 11:47:14 +08:00

@YYSWDD #2 我不是用循环列出来了吗。

noqwerty

2019-04-28 11:50:58 +08:00

@binux #1 补充个好看点的：
for i in range(2**5):
print("{:05b}".format(i))

YYSWDD

2019-04-28 11:57:23 +08:00

@binux #3 我用递归的方式呢。

madao

2019-04-28 12:04:29 +08:00

([1,0]*5).combination(5).to_a.uniq
🤤

SorcererXW

2019-04-28 12:05:29 +08:00

非得使用所谓“算法”的说法，就是把它看成一个 n+1 层的二叉树，先序遍历一遍就好了

holmesabc

2019-04-28 12:09:07 +08:00

第 1 位为 (0, 1), 与 F(剩余的四位所有开关方式) 组合一下。

递归一下

YYSWDD

2019-04-28 12:09:16 +08:00

@binux 考试题目，这么写，会不会被打？

inhzus

2019-04-28 12:14:55 +08:00 via Android

void printPermutation(int depth, string foo) {
if (depth > 5)
return;
else if (depth > 0)
cout << foo << endl;
printPermutation(depth + 1, foo + "1");
printPermutation(depth + 1, foo + "0");
}

手机上写的将就看吧

inhzus

2019-04-28 12:18:07 +08:00 via Android

@inhzus 搞错了
else if (depth == 5)
cout << foo <<endl;

dingyaguang117

2019-04-28 12:19:13 +08:00

估计这题目是希望用 DFS

stevenshuang

2019-04-28 12:19:29 +08:00 via iPhone

cnt = 0
def aux(start, arr):
if start == 5:
global cnt
cnt += 1
print arr
else:
for i in range(2):
arr[start]= i
aux(start+1, arr)
def main():
arr=[0]*5
for i in range(2):
arr[0]=i
aux(1, arr)

main()
print cnt

maggch

2019-04-28 12:21:02 +08:00

这也算算法吗...

behanga

2019-04-28 17:54:58 +08:00

11111 的全排列？

minami

2019-04-28 19:42:54 +08:00

next_permutation，搞定

minami

2019-04-28 19:44:25 +08:00

还可以 bitset

ezksdo

2019-04-28 23:03:17 +08:00

module Main where
import Numeric.Natural
import Prelude hiding ( (^) )

(^) :: [Int] -> Natural -> [[Int]]
a ^ n = f a n [[]]
where
f _ 0 s = s
f a n s = f a (n - 1) ((:) <$> a <*> s)

main :: IO ()
main = print ([0, 1] ^ 5)