Generalized solution to creating k-sized tuples from a collection
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
$begingroup$
In this code for a Set Game, using nested for-loops seems inevitable. But suppose there were more properties to provide for the Card initializer, the pyramid of nested loops would grow even bigger.
A possible solution could be to generate all the possible k-sized tuples from the initial collection, and then loop through them:
func combinations<C: Collection>(sized k: Int, from collection: C) -> [[C.Element]] {
var result: [[C.Element]] = []
var lastCount = 1
while result[result.count - 1].count < k {
for i in result.indices.suffix(lastCount) {
for element in collection {
result.append(result[i] + [element])
}
}
lastCount *= collection.count
}
return Array(result.suffix(lastCount))
}
A deck of cards would be created like so:
struct Card {
let number: Int
let symbol: Int
let color: Int
let shading: Int
}
var deck: [Card] = combinations(sized: 4, from: 1..<3)
.map { Card(number : $0[0],
symbol : $0[1],
color : $0[2],
shading : $0[3])}
The advantage of this approach is that it could be used to concoct tuples with arbitrary size (either greater or less than the collection count) :
combinations(sized: 2, from: "abc") //[["a", "a"], ["a", "b"], ["a", "c"], ["b", "a"], ["b", "b"], ["b", "c"], ["c", "a"], ["c", "b"], ["c", "c"]]
//Or if you're feeling artsy
combinations(sized: 3, from: Set<UIColor>([.red, .yellow, .green, .blue]))
The one limitation is that it quickly goes slow for higher k or collection.count. With n being the number of elements in the collection, there are n + n2 + ... + nk append calls, which makes this an O(nk) algorithm. Is there a better way?
Feedback on all aspects of the code is welcome, such as (but not limited to):
- Time/Space complexity,
- Readability,
- Naming.
performance swift
asked Apr 8 at 19:29
ielyamaniielyamani
377214
$endgroup$
add a comment |
$begingroup$
In this code for a Set Game, using nested for-loops seems inevitable. But suppose there were more properties to provide for the Card initializer, the pyramid of nested loops would grow even bigger.
A possible solution could be to generate all the possible k-sized tuples from the initial collection, and then loop through them:
func combinations<C: Collection>(sized k: Int, from collection: C) -> [[C.Element]] {
var result: [[C.Element]] = []
var lastCount = 1
while result[result.count - 1].count < k {
for i in result.indices.suffix(lastCount) {
for element in collection {
result.append(result[i] + [element])
}
}
lastCount *= collection.count
}
return Array(result.suffix(lastCount))
}
A deck of cards would be created like so:
struct Card {
let number: Int
let symbol: Int
let color: Int
let shading: Int
}
var deck: [Card] = combinations(sized: 4, from: 1..<3)
.map { Card(number : $0[0],
symbol : $0[1],
color : $0[2],
shading : $0[3])}
The advantage of this approach is that it could be used to concoct tuples with arbitrary size (either greater or less than the collection count) :
combinations(sized: 2, from: "abc") //[["a", "a"], ["a", "b"], ["a", "c"], ["b", "a"], ["b", "b"], ["b", "c"], ["c", "a"], ["c", "b"], ["c", "c"]]
//Or if you're feeling artsy
combinations(sized: 3, from: Set<UIColor>([.red, .yellow, .green, .blue]))
The one limitation is that it quickly goes slow for higher k or collection.count. With n being the number of elements in the collection, there are n + n2 + ... + nk append calls, which makes this an O(nk) algorithm. Is there a better way?
Feedback on all aspects of the code is welcome, such as (but not limited to):
- Time/Space complexity,
- Readability,
- Naming.
performance swift
asked Apr 8 at 19:29
ielyamaniielyamani
377214
$endgroup$
$begingroup$
For intro on good k-of-n combinations, I’d refer you to stackoverflow.com/a/127856/1271826. But, while you’re saying “combinations”, it looks like you’re trying to generate n-tuples, i.e. permutations with repetition. Personally, I’d expectcombinations(sized: 2, from: "abc")to generate["a","b"], ["a", "c"], ["b", "c"]. I’m just trying to clarify precisely what you’re looking for.
$endgroup$
– Rob
Apr 9 at 16:07
add a comment |
$begingroup$
In this code for a Set Game, using nested for-loops seems inevitable. But suppose there were more properties to provide for the Card initializer, the pyramid of nested loops would grow even bigger.
A possible solution could be to generate all the possible k-sized tuples from the initial collection, and then loop through them:
func combinations<C: Collection>(sized k: Int, from collection: C) -> [[C.Element]] {
var result: [[C.Element]] = []
var lastCount = 1
while result[result.count - 1].count < k {
for i in result.indices.suffix(lastCount) {
for element in collection {
result.append(result[i] + [element])
}
}
lastCount *= collection.count
}
return Array(result.suffix(lastCount))
}
A deck of cards would be created like so:
struct Card {
let number: Int
let symbol: Int
let color: Int
let shading: Int
}
var deck: [Card] = combinations(sized: 4, from: 1..<3)
.map { Card(number : $0[0],
symbol : $0[1],
color : $0[2],
shading : $0[3])}
The advantage of this approach is that it could be used to concoct tuples with arbitrary size (either greater or less than the collection count) :
combinations(sized: 2, from: "abc") //[["a", "a"], ["a", "b"], ["a", "c"], ["b", "a"], ["b", "b"], ["b", "c"], ["c", "a"], ["c", "b"], ["c", "c"]]
//Or if you're feeling artsy
combinations(sized: 3, from: Set<UIColor>([.red, .yellow, .green, .blue]))
The one limitation is that it quickly goes slow for higher k or collection.count. With n being the number of elements in the collection, there are n + n2 + ... + nk append calls, which makes this an O(nk) algorithm. Is there a better way?
Feedback on all aspects of the code is welcome, such as (but not limited to):
- Time/Space complexity,
- Readability,
- Naming.
performance swift
asked Apr 8 at 19:29
ielyamaniielyamani
377214
$endgroup$
In this code for a Set Game, using nested for-loops seems inevitable. But suppose there were more properties to provide for the Card initializer, the pyramid of nested loops would grow even bigger.
A possible solution could be to generate all the possible k-sized tuples from the initial collection, and then loop through them:
func combinations<C: Collection>(sized k: Int, from collection: C) -> [[C.Element]] {
var result: [[C.Element]] = []
var lastCount = 1
while result[result.count - 1].count < k {
for i in result.indices.suffix(lastCount) {
for element in collection {
result.append(result[i] + [element])
}
}
lastCount *= collection.count
}
return Array(result.suffix(lastCount))
}
A deck of cards would be created like so:
struct Card {
let number: Int
let symbol: Int
let color: Int
let shading: Int
}
var deck: [Card] = combinations(sized: 4, from: 1..<3)
.map { Card(number : $0[0],
symbol : $0[1],
color : $0[2],
shading : $0[3])}
The advantage of this approach is that it could be used to concoct tuples with arbitrary size (either greater or less than the collection count) :
combinations(sized: 2, from: "abc") //[["a", "a"], ["a", "b"], ["a", "c"], ["b", "a"], ["b", "b"], ["b", "c"], ["c", "a"], ["c", "b"], ["c", "c"]]
//Or if you're feeling artsy
combinations(sized: 3, from: Set<UIColor>([.red, .yellow, .green, .blue]))
The one limitation is that it quickly goes slow for higher k or collection.count. With n being the number of elements in the collection, there are n + n2 + ... + nk append calls, which makes this an O(nk) algorithm. Is there a better way?
Feedback on all aspects of the code is welcome, such as (but not limited to):
- Time/Space complexity,
- Readability,
- Naming.
performance swift
performance swift
asked Apr 8 at 19:29
ielyamaniielyamani
377214
asked Apr 8 at 19:29
ielyamaniielyamani
377214
edited 33 mins ago
ielyamani
asked Apr 8 at 19:29
ielyamaniielyamani
377214
asked Apr 8 at 19:29
ielyamaniielyamani
377214
asked Apr 8 at 19:29
ielyamaniielyamani
377214
377214
$begingroup$
For intro on good k-of-n combinations, I’d refer you to stackoverflow.com/a/127856/1271826. But, while you’re saying “combinations”, it looks like you’re trying to generate n-tuples, i.e. permutations with repetition. Personally, I’d expectcombinations(sized: 2, from: "abc")to generate["a","b"], ["a", "c"], ["b", "c"]. I’m just trying to clarify precisely what you’re looking for.
$endgroup$
– Rob
Apr 9 at 16:07
add a comment |
$begingroup$
For intro on good k-of-n combinations, I’d refer you to stackoverflow.com/a/127856/1271826. But, while you’re saying “combinations”, it looks like you’re trying to generate n-tuples, i.e. permutations with repetition. Personally, I’d expectcombinations(sized: 2, from: "abc")to generate["a","b"], ["a", "c"], ["b", "c"]. I’m just trying to clarify precisely what you’re looking for.
$endgroup$
– Rob
Apr 9 at 16:07
$begingroup$
For intro on good k-of-n combinations, I’d refer you to stackoverflow.com/a/127856/1271826. But, while you’re saying “combinations”, it looks like you’re trying to generate n-tuples, i.e. permutations with repetition. Personally, I’d expect
combinations(sized: 2, from: "abc") to generate ["a","b"], ["a", "c"], ["b", "c"]. I’m just trying to clarify precisely what you’re looking for.$endgroup$
– Rob
Apr 9 at 16:07
$begingroup$
For intro on good k-of-n combinations, I’d refer you to stackoverflow.com/a/127856/1271826. But, while you’re saying “combinations”, it looks like you’re trying to generate n-tuples, i.e. permutations with repetition. Personally, I’d expect
combinations(sized: 2, from: "abc") to generate ["a","b"], ["a", "c"], ["b", "c"]. I’m just trying to clarify precisely what you’re looking for.$endgroup$
– Rob
Apr 9 at 16:07
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
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%2fcodereview.stackexchange.com%2fquestions%2f217098%2fgeneralized-solution-to-creating-k-sized-tuples-from-a-collection%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Code Review 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%2fcodereview.stackexchange.com%2fquestions%2f217098%2fgeneralized-solution-to-creating-k-sized-tuples-from-a-collection%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 intro on good k-of-n combinations, I’d refer you to stackoverflow.com/a/127856/1271826. But, while you’re saying “combinations”, it looks like you’re trying to generate n-tuples, i.e. permutations with repetition. Personally, I’d expect
combinations(sized: 2, from: "abc")to generate["a","b"], ["a", "c"], ["b", "c"]. I’m just trying to clarify precisely what you’re looking for.$endgroup$
– Rob
Apr 9 at 16:07