30/09/2018, 23:53
Tạo ID cho mỗi trạng thái của ma trận
Mình có một ma trận nxn . Các phần tử trong ma trận là không thay đổi.Mọi người cho mình hỏi làm sao để với mỗi xáo trộn vị trí các con số của ma trận ta được một ID kiểu int khác nhau không trùng lặp ạ. ID có quan hệ với các phần tử trong ma trận qua các phép toán như nào cũng được miễn là mỗi trạng thái ma trận sẽ có một ID . Mọi người giúp em với nhé .
Bài liên quan
Ý bạn là từ trạng thái mình suy ra được ID. Vậy từ ID có suy ngược ra trạng thái không?
Hiện tại mình không cần suy ngược nhưng nếu được thì thực sự là tốt cũng để mình biết thêm . Bây giờ mình chỉ cần các trạng thái của ma trận giống nhau thì cho ra cùng ID và khác nhau thì khác ID .
kì này mình chuẩn bị học toán rời rạc, mới đọc mấy trang đầu,
1 ma trận n.n để có các trạng thái khác nhau, bạn thử sinh hoán vi, tổ hợp
còn từ ma trận -> id, thì nghĩ 1 quy tắc nào đó,
nhưng nếu yêu cầu từ id -> ma trận thì mắc công hơn ~.~
Theo mình bạn có thể làm như vầy:
Đầu tiên bạn tìm hiểu về các hash functionh giúp chuyển đổi từ string sang một giá trị integer duy nhất (bạn hãy tìm hiểu kĩ thuật toán nào hiệu quả và phù hợp nhất vì theo mình biết, vẫn có khả năng 2 string khác nhau sinh ra cùng một giá trị integer giống nhau). Ý tưởng là ta sẽ tạo một chuỗi từ ma trận bằng cách ghép từng chữ số trong ma trận với nhau (theo thứ tự nào tùy bạn, nhưng phải thống nhất). Từ chuỗi này qua hash function ta sẽ được một số integer.
Thì mình đang muốn các bạn tư vấn cho mình một quy tắc để cho ID tốt nhất mà, mình mà nghĩ ra một quy tắc nào tối ưu thì đâu cần hỏi . Như mình có nghĩ tới một cách lấy ID là có thể lấy các con số của ma trận xếp theo một thứ tự nhất định để được ID .VD như:
Chuyển A[3][3]
3 2 1
4 9 7
8 6 5
Thành ID: 321497865
Cách này chắc chắn cho ID ở mỗi trạng thái khác nhau nhưng thực tế ma trận 3x3 thì chỉ có tối đa 9!=362880 trạng thái tức là ID chỉ cần dao động từ 1 -> 362880 . Nhưng theo cách mà mình nghĩ ID sẽ có thể có giá trị lên tới 987654321 lớn hơn quá nhiều so với cần thiết . Nên mình muốn hỏi một thuật toán tối ưu để tạo được một ID