swift string permutations allowing the same strings
In another question, you ask how to filter the results from dfri's answer (+1) to prune out duplicates resulting from a different order of elements (e.g. if you got a result set with "AAB", "ABA", and "BAA", prune out the latter two).
If that's what you want to do, I'd suggest writing a function that just returned that set of solutions directly:
extension Array where Element: StringProtocol {
/// Return combinations of the elements of the array (ignoring the order of items in those combinations).
///
/// - Parameters:
/// - size: The size of the combinations to be returned.
/// - allowDuplicates: Boolean indicating whether an item in the array can be repeated in the combinations (e.g. is the sampled item returned to the original set or not).
///
/// - Returns: A collection of resulting combinations.
func combinations(size: Int, allowDuplicates: Bool = false) -> [String] {
let n = count
if size > n && !allowDuplicates { return [] }
var combinations: [String] = []
var indices = [0]
var i = 0
while true {
// build out array of indexes (if not complete)
while indices.count < size {
i = indices.last! + (allowDuplicates ? 0 : 1)
if i < n {
indices.append(i)
}
}
// add combination associated with this particular array of indices
combinations.append(indices.map { self[$0] }.joined())
// prepare next one (incrementing the last component and/or deleting as needed
repeat {
if indices.count == 0 { return combinations }
i = indices.last! + 1
indices.removeLast()
} while i > n - (allowDuplicates ? 1 : (size - indices.count))
indices.append(i)
}
}
}
Thus:
let array = ["A", "B", "C", "D"]
let result = array.combinations(size: 2, allowDuplicates: true)
would return:
["AA", "AB", "AC", "AD", "BB", "BC", "BD", "CC", "CD", "DD"]
And if you didn't want it to allow duplicates:
let result = array.combinations(size: 2)
would return:
["AB", "AC", "AD", "BC", "BD", "CD"]
This approach would avoid needing to later filter the results.
Note, I'm sure there are more elegant ways to achieve the above, but hopefully this illustrates the basic idea.
How to generate all possible combinations?
Try this.
The general algorithm is to have a fromList containing the letters you haven't used yet and a toList that is the string you've built up so far. This uses recursion to build up all possible strings and adds them to the set when the length is 2 or greater:
func permute(fromList: [String], toList: [String] = [String](), var set: Set<String> = Set<String>()) -> Set<String> {
if toList.count >= 2 {
set.insert(toList.joinWithSeparator(""))
}
if !fromList.isEmpty {
for (index, item) in fromList.enumerate() {
var newFrom = fromList
newFrom.removeAtIndex(index)
set = permute(newFrom, toList: toList + [item], set: set)
}
}
return set
}
permute(["A", "B", "C"])
// {"BA", "AC", "ABC", "AB", "BCA", "CB", "BC", "CAB", "ACB", "CA", "CBA", "BAC"}
permute(["A", "A", "B"])
// {"BA", "BAA", "AAB", "AB", "ABA", "AA"}
Faster Answer:
As @MartinR pointed out in his post, the solution above is a little slow because of all of the creation and copying of sets. I had originally written this using an inout variable for set, but changed it to the more functional interface to make it nice to call.
Here is my original (faster) implementation, plus I embedded it in a permute that takes just an [String] and returns a Set<String>. It does the work of creating the set and the toList array and then calls the inner version of permute to do the real work:
func permute(list: [String], minStringLen: Int = 2) -> Set<String> {
func permute(fromList: [String], toList: [String], minStringLen: Int, inout set: Set<String>) {
if toList.count >= minStringLen {
set.insert(toList.joinWithSeparator(""))
}
if !fromList.isEmpty {
for (index, item) in fromList.enumerate() {
var newFrom = fromList
newFrom.removeAtIndex(index)
permute(newFrom, toList: toList + [item], minStringLen: minStringLen, set: &set)
}
}
}
var set = Set<String>()
permute(list, toList:[], minStringLen: minStringLen, set: &set)
return set
}
permute(["A", "B", "C"])
// {"BA", "AC", "ABC", "AB", "BCA", "CB", "BC", "CAB", "ACB", "CA", "CBA", "BAC"}
permute(["A", "A", "B"])
// {"BA", "BAA", "AAB", "AB", "ABA", "AA"}
permute(["A", "A", "B"], minStringLen: 1)
// {"BA", "A", "BAA", "AB", "AA", "B", "AAB", "ABA"}
permute(["A", "A", "B"], minStringLen: 3)
// {"ABA", "BAA", "AAB"}
Edit:
I added a minStringLen parameter (with default value of 2) instead of hard coding that value.
See @MartinR's answer for performance comparisons.
Swift 3 and Swift 4:
func permute(list: [String], minStringLen: Int = 2) -> Set<String> {
func permute(fromList: [String], toList: [String], minStringLen: Int, set: inout Set<String>) {
if toList.count >= minStringLen {
set.insert(toList.joined(separator: ""))
}
if !fromList.isEmpty {
for (index, item) in fromList.enumerated() {
var newFrom = fromList
newFrom.remove(at: index)
permute(fromList: newFrom, toList: toList + [item], minStringLen: minStringLen, set: &set)
}
}
}
var set = Set<String>()
permute(fromList: list, toList:[], minStringLen: minStringLen, set: &set)
return set
}
print(permute(list: ["A", "B", "C"]))
// ["ABC", "CA", "BAC", "ACB", "BA", "CAB", "BC", "CB", "BCA", "CBA", "AB", "AC"]
print(permute(list: ["A", "A", "B"]))
// ["AA", "AAB", "ABA", "AB", "BA", "BAA"]
print(permute(list: ["A", "A", "B"], minStringLen: 1))
// ["AAB", "ABA", "B", "BA", "A", "BAA", "AA", "AB"]
print(permute(list: ["A", "A", "B"], minStringLen: 3))
// ["AAB", "ABA", "BAA"]
Find all combination of string array in swift
@yannick's answer is very close.
By computing a Power Set of your set, you obtain all the possible subsets (including your original set and the empty set).
Once you have obtained the Power Set, all you have to do is join the subsets into a single string in order to obtain the result that you're looking for.
Here's the complete solution (along with updated code and plenty of comments):
extension Array {
var powerset: [[Element]] {
guard count > 0 else {
return [[]]
}
// tail contains the whole array BUT the first element
let tail = Array(self[1..<endIndex])
// head contains only the first element
let head = self[0]
// computing the tail's powerset
let withoutHead = tail.powerset
// mergin the head with the tail's powerset
let withHead = withoutHead.map { $0 + [head] }
// returning the tail's powerset and the just computed withHead array
return withHead + withoutHead
}
}
let myArray = ["A", "B", "C", "D"]
print(myArray.powerset) // -> [["D", "C", "B", "A"], ["C", "B", "A"], ["D", "B", "A"], ["B", "A"], ["D", "C", "A"], ["C", "A"], ["D", "A"], ["A"], ["D", "C", "B"], ["C", "B"], ["D", "B"], ["B"], ["D", "C"], ["C"], ["D"], []]
// joining the subsets
let myResult = myArray.powerset.map { $0.sort().joinWithSeparator("") }
print(myResult) // -> ["A", "AB", "ABC", "ABCD", "ABD", "AC", "ACD", "AD", "B", "BC", "BCD", "BD", "C", "CD", "D", ""]
PS
Note that this solution uses a recursive approach, while yours was using an iterative approach.
PPS
If you don't want the empty string "" in your solution, you can just filter it away:
let myResult = myArray.powerset.map({ $0.sort().joinWithSeparator("") }).filter({ $0 != "" })
print(myResult) // -> ["A", "AB", "ABC", "ABCD", "ABD", "AC", "ACD", "AD", "B", "BC", "BCD", "BD", "C", "CD", "D"]
Swift - sorting characters in each string in an array
If you want to take a string, sort its characters, and build a new string from that, in Swift 4 you can:
let string = "foobar"
let sortedString = String(string.sorted())
That results in:
"abfoor"
So, going back to your original problem, you can take you strings, which are a collection of permutations, and build a sorted array of combinations like so:
let permutations = ["AB", "AC", "DC", "CA", "CB"]
// build set of combinations where each string has, itself, been sorted alphabetically
let combinations = Set(permutations.map { String($0.sorted()) })
// convert set (which removed duplicates) back to an array and sort it
let result = Array(combinations).sorted()
That results in:
["AB", "AC", "BC", "CD"]
Permutation with different target vector?
You can do this with expand.grid() like so:
v1 <- c("a","b","c")
v2 <- v1
v3 <- v1
vFull <- expand.grid(v1,v2,v3)
Swift - Generate combinations with repetition
You can get rid of var sub = subcombo by writing the loop as
for subcombo in subcombos {
ret.append([head] + subcombo)
}
This can be further simplified using the map() function:
func combos<T>(var array: Array<T>, k: Int) -> Array<Array<T>> {
if k == 0 {
return [[]]
}
if array.isEmpty {
return []
}
let head = [array[0]]
let subcombos = combos(array, k: k - 1)
var ret = subcombos.map {head + $0}
array.removeAtIndex(0)
ret += combos(array, k: k)
return ret
}
Update for Swift 4:
func combos<T>(elements: ArraySlice<T>, k: Int) -> [[T]] {
if k == 0 {
return [[]]
}
guard let first = elements.first else {
return []
}
let head = [first]
let subcombos = combos(elements: elements, k: k - 1)
var ret = subcombos.map { head + $0 }
ret += combos(elements: elements.dropFirst(), k: k)
return ret
}
func combos<T>(elements: Array<T>, k: Int) -> [[T]] {
return combos(elements: ArraySlice(elements), k: k)
}
Now array slices are passed to the recursive calls to avoid
the creation of many temporary arrays.
Example:
print(combos(elements: [1, 2, 3], k: 2))
// [[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]
Encoding Permutations With Repeating Values
The specific combinations you look for seem to be just "any of A,B,C,D,E on each position".
In this case, they are much akin a "pentary" (base 5) positional numeral system: you have three digits, and each of them may independently be 0 (A), 1 (B), 2 (C), 3 (D), or 4 (E).
The same goes for encoding these as integers: just number them from 0 to 53-1.
For a number k, the "combination" is "(k div 52) mod 5, (k div 51) mod 5, (k div 50) mod 5, with ABCDE encoded as 01234, respectively.
For a "combination" like "xyz", first map letters ABCDE to digits 01234 as x, y, and z, and then the encoding number is x*52 + y*51 + z*50.
Generating all permutations of a given string
public static void permutation(String str) {
permutation("", str);
}
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0) System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
}
}
(via Introduction to Programming in Java)
assign groups depending on pairwise combinations within string
How about the following
# Your data
df <- structure(
list(
id = c(1, 2, 3, 4, 5, 6, 7),
name = c("aa", "ab", "ac", "aa", "aab", "aac", "aabc")),
.Names = c("id", "name"), row.names = c(NA, -7L), class = "data.frame")
# Create all possible 2char combinations from unique chars in string
group <- lapply(strsplit(df$name, ""), function(x)
unique(apply(combn(x, 2), 2, function(y) paste0(y, collapse = ""))));
# Melt and add original data
require(reshape2);
df2 <- melt(group);
df2 <- cbind.data.frame(
df2,
df[match(df2$L1, df$id), ]);
df2$group <- as.numeric(as.factor(df2$value));
df2;
# value L1 id name group
#1 aa 1 1 aa 1
#2 ab 2 2 ab 2
#3 ac 3 3 ac 3
#4 aa 4 4 aa 1
#5 aa 5 5 aab 1
#5.1 ab 5 5 aab 2
#6 aa 6 6 aac 1
#6.1 ac 6 6 aac 3
#7 aa 7 7 aabc 1
#7.1 ab 7 7 aabc 2
#7.2 ac 7 7 aabc 3
#7.3 bc 7 7 aabc 4
Explanation: strsplit splits the strings from df$name into char vectors. combn creates all 2-char combinations based on those char vectors. paste0 and unique keeps the concatenated unique 2-char combinations.
Note that this almost reproduces your example. That's because in my case, aabc also gives rise to group 4 = bc.
Update 1
You can filter entries based on a list of 2-char comparisons
# Filter entries
filter <- c("aa", "ab", "ac");
df2 <- df2[df2$value %in% filter, ]
# Clean up df2 to be consistent with OPs request
df2 <- df2[, -(1:2)];
df2;
# id name group
#1 1 aa 1
#2 2 ab 2
#3 3 ac 3
#4 4 aa 1
#5 5 aab 1
#5.1 5 aab 2
#6 6 aac 1
#6.1 6 aac 3
#7 7 aabc 1
#7.1 7 aabc 2
#7.2 7 aabc 3
Update 2
You can also create a filter dynamically, by selecting those value entries that are represented as 2-char strings in the original dataframe (in this case aa, ab and ac).
filter <- unique(unlist(group[sapply(group, function(x) length(x) == 1)]));
Related Topics
Swift - Segue from Button Inside a Cell
Accurately Get a Color from Pixel on Screen and Convert Its Color Space
Contextmenu on a Rounded Lineargradient Produces Sharp Edges in Swiftui
Different Colors for Bars in Barchart Depend on Value
How to Have Arview and Arscnview Coexist
Swift How to Assign a String to a Uitextfield
How to Deal with Buffered Strings from C in Swift
How to Place Objects with Hit Test Without Plane Detection
Dynamic Uicollectionview Inside Dynamic Uitableviewcell
Calculate Time Difference in Swift 4
Is Dispatchsemaphore a Good Replacement for Nslock
How to Do a Long Press in Swift
Swiftui Widget iOS 14 Gradient Issue
Can Not Conform to Protocol by Creating Extension with Where Clauses