Mapping Subsets to Unique Numbers
$begingroup$
I have set to which I want to map unique numbers to all its subsets. So a function $f(x)$ such that $f$ is 1:1.
Here's the set, but I imagine the method to do this can be generalized - I'd like this one to be used as an example though.
Pick a $n$ such that $n inmathbb{N}$
$$S_n = {(x, y) : x < n,space y = {0, 1},space x in mathbb{N}}$$
An example of the set if $n=2$ looks like this:
$$S_2={(0, 0), (0, 1), (1, 0),(1, 1)} $$
So $f(x) in mathbb{N}$ and $x in P(S_n)$ where $P$ is the power set function.
An example could be something like:
$$f(emptyset) = 0$$
or like this:
$$f({(2, 1),(3,0)}) = 10$$
Thank for the help!
For context, I'm working on a hashing algorithm for a game, and the elements I need to hash have a similar structure to a subset of $S$.
combinatorics
asked Jan 16 at 16:33
LucreciousLucrecious
344
$endgroup$
add a comment |
$begingroup$
I have set to which I want to map unique numbers to all its subsets. So a function $f(x)$ such that $f$ is 1:1.
Here's the set, but I imagine the method to do this can be generalized - I'd like this one to be used as an example though.
Pick a $n$ such that $n inmathbb{N}$
$$S_n = {(x, y) : x < n,space y = {0, 1},space x in mathbb{N}}$$
An example of the set if $n=2$ looks like this:
$$S_2={(0, 0), (0, 1), (1, 0),(1, 1)} $$
So $f(x) in mathbb{N}$ and $x in P(S_n)$ where $P$ is the power set function.
An example could be something like:
$$f(emptyset) = 0$$
or like this:
$$f({(2, 1),(3,0)}) = 10$$
Thank for the help!
For context, I'm working on a hashing algorithm for a game, and the elements I need to hash have a similar structure to a subset of $S$.
combinatorics
asked Jan 16 at 16:33
LucreciousLucrecious
344
$endgroup$
$begingroup$
For hashing, rather use a standard builtin hash function of your object (or of something like json_encode of it)
$endgroup$
– Hagen von Eitzen
Jan 16 at 16:42
$begingroup$
@HagenvonEitzen So, if I were to use the standard builtin hash function, the program would use the pointer and hash that. The problem is that pointers don't contain any information about contents of an object. Two different pointers to two different objects but with equal contents is a definite possibility, and I want my hash to handle that possibility. On the other hand, any encoding that requires more than O(1) to check equality is far too expensive.
$endgroup$
– Lucrecious
Jan 16 at 18:31
add a comment |
$begingroup$
I have set to which I want to map unique numbers to all its subsets. So a function $f(x)$ such that $f$ is 1:1.
Here's the set, but I imagine the method to do this can be generalized - I'd like this one to be used as an example though.
Pick a $n$ such that $n inmathbb{N}$
$$S_n = {(x, y) : x < n,space y = {0, 1},space x in mathbb{N}}$$
An example of the set if $n=2$ looks like this:
$$S_2={(0, 0), (0, 1), (1, 0),(1, 1)} $$
So $f(x) in mathbb{N}$ and $x in P(S_n)$ where $P$ is the power set function.
An example could be something like:
$$f(emptyset) = 0$$
or like this:
$$f({(2, 1),(3,0)}) = 10$$
Thank for the help!
For context, I'm working on a hashing algorithm for a game, and the elements I need to hash have a similar structure to a subset of $S$.
combinatorics
asked Jan 16 at 16:33
LucreciousLucrecious
344
$endgroup$
I have set to which I want to map unique numbers to all its subsets. So a function $f(x)$ such that $f$ is 1:1.
Here's the set, but I imagine the method to do this can be generalized - I'd like this one to be used as an example though.
Pick a $n$ such that $n inmathbb{N}$
$$S_n = {(x, y) : x < n,space y = {0, 1},space x in mathbb{N}}$$
An example of the set if $n=2$ looks like this:
$$S_2={(0, 0), (0, 1), (1, 0),(1, 1)} $$
So $f(x) in mathbb{N}$ and $x in P(S_n)$ where $P$ is the power set function.
An example could be something like:
$$f(emptyset) = 0$$
or like this:
$$f({(2, 1),(3,0)}) = 10$$
Thank for the help!
For context, I'm working on a hashing algorithm for a game, and the elements I need to hash have a similar structure to a subset of $S$.
combinatorics
combinatorics
asked Jan 16 at 16:33
LucreciousLucrecious
344
asked Jan 16 at 16:33
LucreciousLucrecious
344
asked Jan 16 at 16:33
LucreciousLucrecious
344
asked Jan 16 at 16:33
LucreciousLucrecious
344
asked Jan 16 at 16:33
LucreciousLucrecious
344
344
$begingroup$
For hashing, rather use a standard builtin hash function of your object (or of something like json_encode of it)
$endgroup$
– Hagen von Eitzen
Jan 16 at 16:42
$begingroup$
@HagenvonEitzen So, if I were to use the standard builtin hash function, the program would use the pointer and hash that. The problem is that pointers don't contain any information about contents of an object. Two different pointers to two different objects but with equal contents is a definite possibility, and I want my hash to handle that possibility. On the other hand, any encoding that requires more than O(1) to check equality is far too expensive.
$endgroup$
– Lucrecious
Jan 16 at 18:31
add a comment |
$begingroup$
For hashing, rather use a standard builtin hash function of your object (or of something like json_encode of it)
$endgroup$
– Hagen von Eitzen
Jan 16 at 16:42
$begingroup$
@HagenvonEitzen So, if I were to use the standard builtin hash function, the program would use the pointer and hash that. The problem is that pointers don't contain any information about contents of an object. Two different pointers to two different objects but with equal contents is a definite possibility, and I want my hash to handle that possibility. On the other hand, any encoding that requires more than O(1) to check equality is far too expensive.
$endgroup$
– Lucrecious
Jan 16 at 18:31
$begingroup$
For hashing, rather use a standard builtin hash function of your object (or of something like json_encode of it)
$endgroup$
– Hagen von Eitzen
Jan 16 at 16:42
$begingroup$
For hashing, rather use a standard builtin hash function of your object (or of something like json_encode of it)
$endgroup$
– Hagen von Eitzen
Jan 16 at 16:42
$begingroup$
@HagenvonEitzen So, if I were to use the standard builtin hash function, the program would use the pointer and hash that. The problem is that pointers don't contain any information about contents of an object. Two different pointers to two different objects but with equal contents is a definite possibility, and I want my hash to handle that possibility. On the other hand, any encoding that requires more than O(1) to check equality is far too expensive.
$endgroup$
– Lucrecious
Jan 16 at 18:31
$begingroup$
@HagenvonEitzen So, if I were to use the standard builtin hash function, the program would use the pointer and hash that. The problem is that pointers don't contain any information about contents of an object. Two different pointers to two different objects but with equal contents is a definite possibility, and I want my hash to handle that possibility. On the other hand, any encoding that requires more than O(1) to check equality is far too expensive.
$endgroup$
– Lucrecious
Jan 16 at 18:31
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Write $A$ as ${(x_1,y_1), (x_2,y_2), ldots ,(x_k,y_k)}$; each $x_i in {1,2,ldots, n}$ and each $y_i in {0,1}$.
Then set $f(A) = sum_{i=1}^k 2^{2(x_i-1) +y_i}$.
**If instead each $x_i in {0,2,ldots, n-1}$ and everything else as before then set $f(A) = sum_{i=1}^k 2^{2x_i +y_i}$.
The idea is that the binary expansion of $f(A)$ gives $A$ explicitly: For each ordered pair $(x,y) in S_n$, the element $(x,y)$ is in $A$ iff the $[2(x-1)+y]$-th bit of $f(A)$ is 1. [Given $(x,y),(x',y') in S_n$, note that $2(x'-1)+y' not = 2(x-1)+y$ iff $(x,y) not = (x',y')$.]
answered Jan 16 at 18:31
MikeMike
4,611512
$endgroup$
$begingroup$
This is nice! Note that $x_i$ may be zero, so you should probably remove the $(x_i - 1)$ part.
$endgroup$
– Vincent
Jan 16 at 21:39
$begingroup$
Sure. My understanding is that $x_i in {1,ldots, n}$. In any case I did edit in case $x_i in {0,1,ldots, n-1}$.
$endgroup$
– Mike
Jan 16 at 21:41
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3075944%2fmapping-subsets-to-unique-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Write $A$ as ${(x_1,y_1), (x_2,y_2), ldots ,(x_k,y_k)}$; each $x_i in {1,2,ldots, n}$ and each $y_i in {0,1}$.
Then set $f(A) = sum_{i=1}^k 2^{2(x_i-1) +y_i}$.
**If instead each $x_i in {0,2,ldots, n-1}$ and everything else as before then set $f(A) = sum_{i=1}^k 2^{2x_i +y_i}$.
The idea is that the binary expansion of $f(A)$ gives $A$ explicitly: For each ordered pair $(x,y) in S_n$, the element $(x,y)$ is in $A$ iff the $[2(x-1)+y]$-th bit of $f(A)$ is 1. [Given $(x,y),(x',y') in S_n$, note that $2(x'-1)+y' not = 2(x-1)+y$ iff $(x,y) not = (x',y')$.]
answered Jan 16 at 18:31
MikeMike
4,611512
$endgroup$
$begingroup$
This is nice! Note that $x_i$ may be zero, so you should probably remove the $(x_i - 1)$ part.
$endgroup$
– Vincent
Jan 16 at 21:39
$begingroup$
Sure. My understanding is that $x_i in {1,ldots, n}$. In any case I did edit in case $x_i in {0,1,ldots, n-1}$.
$endgroup$
– Mike
Jan 16 at 21:41
add a comment |
$begingroup$
Write $A$ as ${(x_1,y_1), (x_2,y_2), ldots ,(x_k,y_k)}$; each $x_i in {1,2,ldots, n}$ and each $y_i in {0,1}$.
Then set $f(A) = sum_{i=1}^k 2^{2(x_i-1) +y_i}$.
**If instead each $x_i in {0,2,ldots, n-1}$ and everything else as before then set $f(A) = sum_{i=1}^k 2^{2x_i +y_i}$.
The idea is that the binary expansion of $f(A)$ gives $A$ explicitly: For each ordered pair $(x,y) in S_n$, the element $(x,y)$ is in $A$ iff the $[2(x-1)+y]$-th bit of $f(A)$ is 1. [Given $(x,y),(x',y') in S_n$, note that $2(x'-1)+y' not = 2(x-1)+y$ iff $(x,y) not = (x',y')$.]
answered Jan 16 at 18:31
MikeMike
4,611512
$endgroup$
$begingroup$
This is nice! Note that $x_i$ may be zero, so you should probably remove the $(x_i - 1)$ part.
$endgroup$
– Vincent
Jan 16 at 21:39
$begingroup$
Sure. My understanding is that $x_i in {1,ldots, n}$. In any case I did edit in case $x_i in {0,1,ldots, n-1}$.
$endgroup$
– Mike
Jan 16 at 21:41
add a comment |
$begingroup$
Write $A$ as ${(x_1,y_1), (x_2,y_2), ldots ,(x_k,y_k)}$; each $x_i in {1,2,ldots, n}$ and each $y_i in {0,1}$.
Then set $f(A) = sum_{i=1}^k 2^{2(x_i-1) +y_i}$.
**If instead each $x_i in {0,2,ldots, n-1}$ and everything else as before then set $f(A) = sum_{i=1}^k 2^{2x_i +y_i}$.
The idea is that the binary expansion of $f(A)$ gives $A$ explicitly: For each ordered pair $(x,y) in S_n$, the element $(x,y)$ is in $A$ iff the $[2(x-1)+y]$-th bit of $f(A)$ is 1. [Given $(x,y),(x',y') in S_n$, note that $2(x'-1)+y' not = 2(x-1)+y$ iff $(x,y) not = (x',y')$.]
answered Jan 16 at 18:31
MikeMike
4,611512
$endgroup$
Write $A$ as ${(x_1,y_1), (x_2,y_2), ldots ,(x_k,y_k)}$; each $x_i in {1,2,ldots, n}$ and each $y_i in {0,1}$.
Then set $f(A) = sum_{i=1}^k 2^{2(x_i-1) +y_i}$.
**If instead each $x_i in {0,2,ldots, n-1}$ and everything else as before then set $f(A) = sum_{i=1}^k 2^{2x_i +y_i}$.
The idea is that the binary expansion of $f(A)$ gives $A$ explicitly: For each ordered pair $(x,y) in S_n$, the element $(x,y)$ is in $A$ iff the $[2(x-1)+y]$-th bit of $f(A)$ is 1. [Given $(x,y),(x',y') in S_n$, note that $2(x'-1)+y' not = 2(x-1)+y$ iff $(x,y) not = (x',y')$.]
answered Jan 16 at 18:31
MikeMike
4,611512
edited Jan 16 at 22:02
answered Jan 16 at 18:31
MikeMike
4,611512
answered Jan 16 at 18:31
MikeMike
4,611512
answered Jan 16 at 18:31
MikeMike
4,611512
4,611512
$begingroup$
This is nice! Note that $x_i$ may be zero, so you should probably remove the $(x_i - 1)$ part.
$endgroup$
– Vincent
Jan 16 at 21:39
$begingroup$
Sure. My understanding is that $x_i in {1,ldots, n}$. In any case I did edit in case $x_i in {0,1,ldots, n-1}$.
$endgroup$
– Mike
Jan 16 at 21:41
add a comment |
$begingroup$
This is nice! Note that $x_i$ may be zero, so you should probably remove the $(x_i - 1)$ part.
$endgroup$
– Vincent
Jan 16 at 21:39
$begingroup$
Sure. My understanding is that $x_i in {1,ldots, n}$. In any case I did edit in case $x_i in {0,1,ldots, n-1}$.
$endgroup$
– Mike
Jan 16 at 21:41
$begingroup$
This is nice! Note that $x_i$ may be zero, so you should probably remove the $(x_i - 1)$ part.
$endgroup$
– Vincent
Jan 16 at 21:39
$begingroup$
This is nice! Note that $x_i$ may be zero, so you should probably remove the $(x_i - 1)$ part.
$endgroup$
– Vincent
Jan 16 at 21:39
$begingroup$
Sure. My understanding is that $x_i in {1,ldots, n}$. In any case I did edit in case $x_i in {0,1,ldots, n-1}$.
$endgroup$
– Mike
Jan 16 at 21:41
$begingroup$
Sure. My understanding is that $x_i in {1,ldots, n}$. In any case I did edit in case $x_i in {0,1,ldots, n-1}$.
$endgroup$
– Mike
Jan 16 at 21:41
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3075944%2fmapping-subsets-to-unique-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
For hashing, rather use a standard builtin hash function of your object (or of something like json_encode of it)
$endgroup$
– Hagen von Eitzen
Jan 16 at 16:42
$begingroup$
@HagenvonEitzen So, if I were to use the standard builtin hash function, the program would use the pointer and hash that. The problem is that pointers don't contain any information about contents of an object. Two different pointers to two different objects but with equal contents is a definite possibility, and I want my hash to handle that possibility. On the other hand, any encoding that requires more than O(1) to check equality is far too expensive.
$endgroup$
– Lucrecious
Jan 16 at 18:31