thắc mắc Làm thế nào để liệt kê tất cả các số có 3 chữ số khác nhau

rosario_1

Member
Câu hỏi như trên. Idea hiện tại của tớ là

for (int i=1;i<=9;i++)
for (int j=0;j<=9;j++)
for (int k=0;k<=9;k++)
if(i!=j && i!=k && j!=k) v.v...

Bây giờ nên viết lại đống này như thế nào cho gọn? Bởi giờ nếu tớ muốn mở rộng thuật toán này lên cho 4 số thì sẽ cần 4 vòng for và check đủ i!=j, i!=k,i!=l,j!=k,j!=l,k!=l; nhìn rất thô
 

cuuduongthancong.com

Junior Member
Mình thấy bài toán này thuộc dạng "liệt kê các chỉnh hợp không lặp chập k" của n phần tử. Trường hợp ví dụ ở trên là n=9 và k=3 . Trong quyển giải thuật và lập trình của thầy Lê Minh Hoàng có đề cập cách giải bằng ngôn ngữ Pascal ở phần 1-Bài Toán Liệt Kê mục 3.3.
Trang rebvn có giải thích và hiện thực lại bằng ngôn ngữ c.

Mình có copy và sửa lại bằng Java test lại thấy ổn
public static void main(String[] args) throws IOException, Exception {
int n = 2;
int k = 2;
int[] mang = new int[n];
boolean[] check = new boolean[n];
//khởi tạo mảng
for (int i = 0; i < n; i++) {
mang = i;
check = true;
}
// int[] mang = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// boolean[] check = {true, true, true, true, true, true, true, true, true};
Try(n, k, mang, 0, check);
}

static void Try(int n, int k, int[] mang, int i, boolean[] check) {
int j;
for (j = 0; j < n; j++) {
if (check[j] == true) // nếu chưa được gán cho các vị trí phía trước
{
mang = j + 1;
check[j] = false; // đổi lại thành false để các vị trí sau không được dùng nữa

if (i == (k - 1)) {
int temp;
for (temp = 0; temp < k; temp++) {
System.out.print(mang[temp] + " ");
}
System.out.println();
} else {
Try(n, k, mang, i + 1, check);
}

check[j] = true; // gán lại thành true để vì vị trí i hiện sắp tới không sử dụng giá trị j nữa.
}
}

}
 

rosario_1

Member
Rất cảm ơn bạn nhưng cá nhân mình không nghĩ đến đệ quy quay lui vì với đề bài thế kia bởi thuật toán nó trở thành quá phức tạp so với vấn đề nó giải quyết, thành ra đại bác bắn sẻ.

Cái mình muốn tìm kiếm là 1 lời giải "đẹp" tương xứng với tầm vóc của vấn đề, có nghĩa là số dòng lệnh càng ít và càng đơn giản càng tốt. Kiểu như súng cao su bắn sẻ ấy.
 

omyto

Junior Member
C++:
int8_t size = 4;
uint32_t begin = [&]() -> uint32_t { uint32_t x = 1; for (int i = 0; i < size - 1; i++) x *= 10; return x; }();
uint32_t end = [&]() -> uint32_t { uint32_t x = 1; for (int i = 0; i < size; i++) x *= 10; return x - 1; }();

for (uint32_t i = begin; i <= end; i++) {
  std::set<int8_t> set;
  uint32_t num = i;
  for (int8_t j = 0; j < size; j++) {
    set.insert(num % 10);
    num = num / 10;
  }
  if (set.size() == size) {
    LOGI("%u", i);
  }
}
Không biết có "đẹp" không, nhưng mình thích làm thủ công kiểu này hơn :D
 

dangmt

Junior Member
Rất cảm ơn bạn nhưng cá nhân mình không nghĩ đến đệ quy quay lui vì với đề bài thế kia bởi thuật toán nó trở thành quá phức tạp so với vấn đề nó giải quyết, thành ra đại bác bắn sẻ.

Cái mình muốn tìm kiếm là 1 lời giải "đẹp" tương xứng với tầm vóc của vấn đề, có nghĩa là số dòng lệnh càng ít và càng đơn giản càng tốt. Kiểu như súng cao su bắn sẻ ấy.
Đệ quy là đơn giản nhất rồi. Đệ quy mà còn nghĩ là đại bác thì chịu. Đệ quy là nền tảng của lập trình. Cái này còn đơn giản hơn cả súng cao su ấy.
 

trungpham90

Đã tốn tiền
Dùng dynamic programming + bitmask technique.

Dùng recursive thì độ phức tạp thuật toán sẽ rất lớn.

Hoặc dùng tổ hợp rất đơn giản.

À lộn bài đếm. Nếu liệt kê thì cứ trâu bò thôi.
 

vanfsn

Member
Mình thấy bài toán này thuộc dạng "liệt kê các chỉnh hợp không lặp chập k" của n phần tử. Trường hợp ví dụ ở trên là n=9 và k=3 . Trong quyển giải thuật và lập trình của thầy Lê Minh Hoàng có đề cập cách giải bằng ngôn ngữ Pascal ở phần 1-Bài Toán Liệt Kê mục 3.3.
Trang rebvn có giải thích và hiện thực lại bằng ngôn ngữ c.

Mình có copy và sửa lại bằng Java test lại thấy ổn
public static void main(String[] args) throws IOException, Exception {
int n = 2;
int k = 2;
int[] mang = new int[n];
boolean[] check = new boolean[n];
//khởi tạo mảng
for (int i = 0; i < n; i++) {
mang = i;
check = true;
}
// int[] mang = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// boolean[] check = {true, true, true, true, true, true, true, true, true};
Try(n, k, mang, 0, check);
}

static void Try(int n, int k, int[] mang, int i, boolean[] check) {
int j;
for (j = 0; j < n; j++) {
if (check[j] == true) // nếu chưa được gán cho các vị trí phía trước
{
mang = j + 1;
check[j] = false; // đổi lại thành false để các vị trí sau không được dùng nữa

if (i == (k - 1)) {
int temp;
for (temp = 0; temp < k; temp++) {
System.out.print(mang[temp] + " ");
}
System.out.println();
} else {
Try(n, k, mang, i + 1, check);
}

check[j] = true; // gán lại thành true để vì vị trí i hiện sắp tới không sử dụng giá trị j nữa.
}
}

}
Đạo hữu à,
1591160721431.png
 
9*9*8=648 số có 3 chữ số khác nhau đơn giản hơn cái Chỉnh hợp.

Code bằng mồm thì đơn giản nhất thì dùng 1 vòng for 102=>987, bỏ số trùng hàng trăm với hàng chục hoặc hàng chục với hàng đơn vị hoặc hàng chục với hàng đơn vị.

P/S: còn ông kẹ nào nói Tổ hợp thì bậy vì (9,8,7) (9,7,8) (7,8,9) .......3! = 6 số đc tính chỉ là 1 vì nó không phân biệt thứ tự. Đúng ra là dùng Chỉnh hợp => 10*9*8 - 9*8
 
Last edited:

fivelions

Junior Member
9*9*8=648 số có 3 chữ số khác nhau đơn giản hơn cái Chỉnh hợp.

Code bằng mồm thì đơn giản nhất thì dùng 1 vòng for 102=>987, bỏ số trùng hàng trăm với hàng chục hoặc hàng chục với hàng đơn vị hoặc hàng chục với hàng đơn vị.

P/S: còn ông kẹ nào nói Tổ hợp thì bậy vì (9,8,7) (9,7,8) (7,8,9) .......3! = 6 số đc tính chỉ là 1 vì nó không phân biệt thứ tự. Đúng ra là dùng Chỉnh hợp => 10*9*8 - 9*8
Code = cách của thím ko scalable đc, như #2 là hợp lí, limit đầu vào >0 & <10 số là xong.
 

trungpham90

Đã tốn tiền
9*9*8=648 số có 3 chữ số khác nhau đơn giản hơn cái Chỉnh hợp.

Code bằng mồm thì đơn giản nhất thì dùng 1 vòng for 102=>987, bỏ số trùng hàng trăm với hàng chục hoặc hàng chục với hàng đơn vị hoặc hàng chục với hàng đơn vị.

P/S: còn ông kẹ nào nói Tổ hợp thì bậy vì (9,8,7) (9,7,8) (7,8,9) .......3! = 6 số đc tính chỉ là 1 vì nó không phân biệt thứ tự. Đúng ra là dùng Chỉnh hợp => 10*9*8 - 9*8
Tôi bảo tổ hợp gợi ý thôi, j mà căng? Bt gọi tắt toán tổ hợp chứ ai gọi toán chỉnh hợp?
 
Scalable? Giờ muốn giải tổng quát hơn như 4 / 5 số và hệ cơ số thập lục phân hexadecimal thì cũng vậy thôi, miễn nhìn ra cái pattern rồi scale up lên
for 10234 => FEDCB
Số lần lặp là FEDCB - 10234 + 1 = EEB98
Dễ hem?
 

trungpham90

Đã tốn tiền
Có công thức mà phen, kA10 - (k-1)A9. Ko biết ở Vn h dùng A hay dùng P? k là số chữ số, k <= 10
 

cba

Member
Câu hỏi như trên. Idea hiện tại của tớ là

for (int i=1;i<=9;i++)
for (int j=0;j<=9;j++)
for (int k=0;k<=9;k++)
if(i!=j && i!=k && j!=k) v.v...

Bây giờ nên viết lại đống này như thế nào cho gọn? Bởi giờ nếu tớ muốn mở rộng thuật toán này lên cho 4 số thì sẽ cần 4 vòng for và check đủ i!=j, i!=k,i!=l,j!=k,j!=l,k!=l; nhìn rất thô
Đằng nào chẳng phải liệt kê hết 999.
X <=999 && >= 99
For x++
Std::cout x;
 

xmentin2

Junior Member
liệt kê hết vào 1 array thì chỉ 2 loop thôi

JavaScript:
let max = '9'.repeat(3);
let arr = [];
max = parseInt(max);

for(let i=1; i<=max) {
    let i_str = i.toString().split('');
    let check_flg = true;

    for(let j=0; j<(i_str.length-1); j++){
        let char = i_str[j];
        let first = i_str.indexOf(char);
        let last = i_str.lastIndexOf(char);
        if(first != last){
            check_flg = false;
        }
    }

    if(check_flg) arr.push(i);
}
console.log(arr);

Code trên mobile có lỗi bác fix nốt :big_smile:
 
Last edited:

linhusp3

Junior Member
1 cách khá đơn giản mà ko dùng đệ quy là dùng sàng. Sàng chủ yếu để liệt kê số nguyên tố nhưng mấy bài ntn xài cũng khá ổn

Python:
def main(length=3):
    end = 10**length
    start = 10**(length - 1)
    unique_mask = [i >= start and is_unique(i) for i in range(end)]
    print([i for i in range(end) if unique_mask[i]])


def is_unique(i):
    counted = [False for i in range(10)]
    while i != 0:
        digit = i % 10
        if counted[digit]:
            return False
        counted[digit] = True
        i //= 10
    return True


if __name__ == "__main__":
    main(3)
 
Last edited:

linhusp3

Junior Member
Cứu đôi mắt của những ông vào sau
Mình thấy bài toán này thuộc dạng "liệt kê các chỉnh hợp không lặp chập k" của n phần tử. Trường hợp ví dụ ở trên là n=9 và k=3 . Trong quyển giải thuật và lập trình của thầy Lê Minh Hoàng có đề cập cách giải bằng ngôn ngữ Pascal ở phần 1-Bài Toán Liệt Kê mục 3.3.
Trang rebvn có giải thích và hiện thực lại bằng ngôn ngữ c.

Mình có copy và sửa lại bằng Java test lại thấy ổn
Java:
public static void main(String[] args) throws IOException, Exception {
    int n = 2;
    int k = 2;
    int[] mang = new int[n];
    boolean[] check = new boolean[n];

    // khởi tạo mảng
    for (int i = 0; i < n; i++) {
        mang = i;
        check = true;
    }

    int[] mang = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    boolean[] check = {true, true, true, true, true, true, true, true, true};
    Try(n, k, mang, 0, check);
}


static void Try(int n, int k, int[] mang, int i, boolean[] check) {
    int j;
    for (j = 0; j < n; j++) {
        if (check[j] == true) // nếu chưa được gán cho các vị trí phía trước {
            mang = j + 1;
            check[j] = false; // đổi lại thành false để các vị trí sau không được dùng nữa
            if (i == (k - 1)) {
                int temp;
                for (temp = 0; temp < k; temp++) {
                    System.out.print(mang[temp] + " ");
                }
                System.out.println();
            } else {
                Try(n, k, mang, i + 1, check);
            }
            check[j] = true; // gán lại thành true để vì vị trí i hiện sắp tới không sử dụng giá trị j nữa.
        }
    }
}
 

zulu

Member
Rất cảm ơn bạn nhưng cá nhân mình không nghĩ đến đệ quy quay lui vì với đề bài thế kia bởi thuật toán nó trở thành quá phức tạp so với vấn đề nó giải quyết, thành ra đại bác bắn sẻ.

Cái mình muốn tìm kiếm là 1 lời giải "đẹp" tương xứng với tầm vóc của vấn đề, có nghĩa là số dòng lệnh càng ít và càng đơn giản càng tốt. Kiểu như súng cao su bắn sẻ ấy.
Cho hỏi bác tên thành ợ?

via nextVOZ for iPhone
 

mistake37

Member
Liệt kê thì cứ 1 vòng for mà táng thôi. :rolleyes:

pseudo:
Code:
for int i=n;i<m;i++{
 if check(i) {
      println(i)
}
}
Sent from Soupie using vozFApp
 

dogamer01

Member
Câu hỏi như trên. Idea hiện tại của tớ là

for (int i=1;i<=9;i++)
for (int j=0;j<=9;j++)
for (int k=0;k<=9;k++)
if(i!=j && i!=k && j!=k) v.v...

Bây giờ nên viết lại đống này như thế nào cho gọn? Bởi giờ nếu tớ muốn mở rộng thuật toán này lên cho 4 số thì sẽ cần 4 vòng for và check đủ i!=j, i!=k,i!=l,j!=k,j!=l,k!=l; nhìn rất thô
À thế thì cũng đơn giản

Rất cảm ơn bạn nhưng cá nhân mình không nghĩ đến đệ quy quay lui vì với đề bài thế kia bởi thuật toán nó trở thành quá phức tạp so với vấn đề nó giải quyết, thành ra đại bác bắn sẻ.

Cái mình muốn tìm kiếm là 1 lời giải "đẹp" tương xứng với tầm vóc của vấn đề, có nghĩa là số dòng lệnh càng ít và càng đơn giản càng tốt. Kiểu như súng cao su bắn sẻ ấy.
Em xin phép đoán là for tất cả các số có dạng n chữ số
Xong tách từng c/s
Dùng mảng đánh dấu 10 c/s từ 0 đến 9
Nếu có cái nào đc đánh dấu > 1 lần mỗi lần tách là loại
Ngu kiến của em :)

Đệ quy là đơn giản nhất rồi. Đệ quy mà còn nghĩ là đại bác thì chịu. Đệ quy là nền tảng của lập trình. Cái này còn đơn giản hơn cả súng cao su ấy.
Thật ra giải đơn giản hơn đệ quy thì nghĩ tí là đc :)
 
Top