Bitwise thay đổi để tạo ra tất cả các hoán vị có thể trong C

Question

thể trùng lặp:
Creating multiple numbers with certain number of bits set

Tôi đang cố gắng để viết một số mã mà sẽ đưa từng kết hợp có thể có của các số trong một mảng bằng chuyển bit qua.

Ví dụ, tôi muốn tìm tất cả kết hợp có thể có của 3 bit (nơi tối đa một chữ số có thể được 6) mảng nên chứa:

000111 
001011 
001101 
001110 
010011 
010101 
010110 
011001 
011010 
011100 
100011

Và vân vân ...

Từ những gì tôi đã giải thích, khi bit vị trí cuối cùng là 1, chúng tôi thay đổi số bằng 1 (x >> 1) và thêm 1 ở đầu. Tuy nhiên, tôi không chắc chắn làm thế nào để mã phần còn lại. Tôi đang sử dụng C để viết này. Ngoài ra - theo như tôi có thể nói đây là một chuỗi colex, tuy nhiên, tôi là tất cả các tai nếu có một chuỗi khác sẽ cho tôi kết quả cuối cùng (mảng với tất cả các kết hợp k-bit có thể có với một ràng buộc của N).

Answer 1

Bạn có thể giải quyết vấn đề này bằng cách tạo các trình tự đệ quy.

Chúng ta hãy định nghĩa một hàm đệ quy f(int index, int bits, int number) rằng sẽ mất trong hiện tại index của các bit và số lượng bits trái sang nơi khác, và number tạo ra cho đến nay. Sau đó, bạn có tùy chọn thiết lập bit hiện tại thành 1 hoặc 0 và đệ quy từ đó.

Nhìn chung, mức độ phức tạp thời gian nên O (số trình tự), hoặc O (N chọn B), trong đó N là số chữ số và B là số bit thiết lập để 1.

Chức năng như sau:

void f(int index, int bits, int number) { 
    if (index == 0) { 
     if (bits == 0) { // all required bits have been used 
      emit_answer(number); // chuck number into an array, print it, whatever. 
     } 
     return; 
    } 

    if (index-1 >= bits) { // If we can afford to put a 0 here 
     f(index-1, bits, number); 
    } 

    if (bits > 0) { // If we have any 1s left to place 
     f(index-1, bits-1, number | (1 << (index-1))); 
    } 
} 

// to call: 
f(6, 3, 0); 

Đối với N,B = 6,3 kết quả phù hợp với bạn và được sắp xếp theo thứ tự. Liên kết tới ví dụ hoạt động: http://codepad.org/qgd689ZM

Answer 2

Có lẽ một cách hiệu quả hơn, nhưng bạn chỉ có thể lặp qua các con số và từ chối các số không có số lượng bit là 3? Xem this answer để đếm bit.

Answer 3

Không cần bất kỳ đệ quy lạ mắt nào. Một số toán học đơn giản sẽ đủ (một phân chia bởi một giá trị mà sẽ luôn luôn là một sức mạnh của hai là bắt buộc).

 
    Function nextBits(ByVal prevVal As Integer) 
     Dim lsOne As Integer = ((prevVal - 1) And Not prevVal) + 1 
     Dim nextZero As Integer = (prevVal + lsOne) And Not prevVal 
     Dim lowBits As Integer = ((nextZero \ lsOne \ 2) - 1) 
     Return prevVal + lsOne + lowBits 
    End Function 

Đẹp và dễ dàng.