Thuật toán liệt kê các chuỗi khác nhau từ các kí tự ban đầu
Xin chào mọi người, mình có 1 thuật toán này mà chưa tìm được phương pháp tối ưu, mong mọi người giúp đỡ. input: cho 12 kí tự : A,B,C,D,E,F,G,H,I,J,K,L output: liệt kê các chuỗi khác nhau bao gồm 7 kí tự được lấy từ 12 kí tự trên, ví dụ :
- A,A,A,A,A,A,A
- A,A,A,A,A,A,B 3.A,A,A,A,A,B,A .... .... (n). L,L,L,L,L,L,L
bài toán trên giống bài toán lớp 11. Cho các số tự nhiên 1,2,3,4,5,6,7,8,9 liệt kê tất cả các số gồm 4 chữ số. vd: 1111, 1112, 1121, 1211, 2111.... 9999 Cho mình xin hướng giải quyết với ạ, mình cảm ơn ạ!
1 CÂU TRẢ LỜI
Nếu bạn dùng Python thì khá đơn giản:
from itertools import product
for chars in product('ABCDEFGHIJKL', repeat=7):
print(''.join(chars))
Còn không thì có cách khác Đó là để ý mỗi chữ cái có 12 trường hợp, giống như các số base-12:
def i2b12(i: int):
res = [0] * 7
for idx in range(7):
res[6 - idx] = i % 12
i //= 12
return res
for i in range(12 ** 7):
print(''.join('ABCDEFGHIJKL'[x] for x in i2b12(i)))
Bạn có thể optimize bằng cách tăng dần idxs
mà không phải tính lại base-12 representation mỗi lần, nhưng nó lằng nhằng nên sẽ để bạn tự tìm hiểu
oh, không biết bên javascript, C, php có không nhỉ, cảm ơn bạn nha, để mình cài python chạy thử
@ngoctnq mình đọc python ko hiểu lắm, để mình tìm hiểu thêm, cảm ơn bạn nhiều nha, mình đang muốn viết bằng js á
@hoangkim1982 2 bên đó đều tương tự nhé bạn: ví dụ bên C:
#include <stdio.h>
#include <math.h>
int main() {
unsigned int i, num;
int j;
char string[7];
for (i = 0; i < pow(12, 7); ++i) {
num = i;
for (j = 6; j >= 0; --j) {
string[j] = (char) ((int)'A' + num % 12);
num /= 12;
}
printf("%s\n", string);
}
return 0;
}
@hoangkim1982 còn code JS thì như sau:
let i, j, val;
for (i = 0; i < Math.pow(12, 7); ++i) {
let s = "";
val = i;
for (j = 6; j >= 0; --j) {
// 65 is charcode of 'A'
s = String.fromCharCode(65 + val % 12) + s;
val /= 12;
}
console.log(s);
}
@ngoctnq cảm ơn bạn nhiều nhé, mình hiểu rồi
@ngoctnq ah cái input mình ví dụ là chữ cái A,B,C vậy thôi còn thực tế nó là tên người đó cậu, ví dụ Hiep, Tien, Hoa.... thì cách trên bạn viết bằng js đó phải gán vào 1 mảng ví dụ A => Hiep, B => Tien đúng ko c nhỉ
@hoangkim1982 à đúng rồi nhé, thay đổi chút xíu thôi, dùng indexing thay vì char + xài list thay vì string