How to get all possible combinations of a list’s elements?
Have a look at itertools.combinations:
itertools.combinations(iterable, r)
Return r length subsequences of elements from
the input iterable.Combinations are emitted in lexicographic sort order. So, if the
input iterable is sorted, the
combination tuples will be produced in
sorted order.
Since 2.6, batteries are included!
Getting all possible combination for [1,0] with length 3 [0,0,0] to [1,1,1]
You're looking for a Cartesian product, not a combination or permutation of [0, 1]
. For that, you can use itertools.product
.
from itertools import product
items = [0, 1]
for item in product(items, repeat=3):
print(item)
This produces the output you're looking for (albeit in a slightly different order):
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
How to generate all possible combinations from the letters of strings in a list
I can propose you a trivial algorithm to do the same, it is using recursion:
def associations(entry):
while len(entry) > 2:
to_treat_later = entry.pop()
print(f"We will treat {to_treat_later} later")
entry = associations(entry)
entry.append(to_treat_later)
else:
print(f"we can start with {entry}")
associated_entry = []
for elt_1 in entry[0]:
for elt_2 in entry[1]:
associated_entry.append(f"{elt_1}{elt_2}")
return [associated_entry]
def convert_entry(entry):
converted_entry = []
for elt in entry:
list_elt = []
for letter in elt:
list_elt.append(letter)
converted_entry.append(list_elt)
return converted_entry
the_entry = ["jkl", "ghi", "def", "cfe"]
associations(convert_entry(the_entry))
How to generate all the possible combinations for a list of elements grouped in different sizes?
You should take a look at the more-itertools library. And more particularly to the set_partitions method that should suits your needs.
from more-itertools import set_partitions
fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']
for itm in set_partitions(fruits)):
print(itm)
The ouput produce is :
[['Apple', 'Orange', 'Banana', 'Watermelon']]
[['Apple'], ['Orange', 'Banana', 'Watermelon']]
[['Apple', 'Orange'], ['Banana', 'Watermelon']]
[['Orange'], ['Apple', 'Banana', 'Watermelon']]
[['Apple', 'Orange', 'Banana'], ['Watermelon']]
[['Orange', 'Banana'], ['Apple', 'Watermelon']]
[['Apple', 'Banana'], ['Orange', 'Watermelon']]
[['Banana'], ['Apple', 'Orange', 'Watermelon']]
[['Apple'], ['Orange'], ['Banana', 'Watermelon']]
[['Apple'], ['Orange', 'Banana'], ['Watermelon']]
[['Apple'], ['Banana'], ['Orange', 'Watermelon']]
[['Apple', 'Orange'], ['Banana'], ['Watermelon']]
[['Orange'], ['Apple', 'Banana'], ['Watermelon']]
[['Orange'], ['Banana'], ['Apple', 'Watermelon']]
[['Apple'], ['Orange'], ['Banana'], ['Watermelon']]
EDIT:
And if you want all every combinations possible if you reorder your orignal list you can use the previous method in combination with the the permutations method of itertools with something like:
import itertools
from more_itertools import set_partitions
fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']
output = list()
for x in itertools.permutations(fruits):
output += list(set_partitions(x))
How to create all combinations for items in an Array?
If the task is not to implement the algorithm which generates the permutations you need, I would recomend to use a library like combinatoricslib3. If you happen to use Guava or Apache Commons in your projects, those have also some methods to generate combinations / permutations from a given collection. With combinatoricslib3 your code could look something like:
import org.paukov.combinatorics3.Generator;
public class Example {
public static void main(String[] args) {
Integer[] array = {1,2,3,4};
Generator.permutation(array)
.simple()
.stream()
.forEach(System.out::println);
//Example with strings
Generator.permutation("apple", "orange", "cherry")
.simple()
.stream()
.forEach(System.out::println);
}
}
output:
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[4, 1, 3, 2]
....
and
[apple, orange, cherry]
[apple, cherry, orange]
[cherry, apple, orange]
[cherry, orange, apple]
[orange, cherry, apple]
[orange, apple, cherry]
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"]
Related Topics
Core Data: Delete All Objects of an Entity Type, Ie Clear a Table
How to Install the "App Store" in an iOS Simulator
How to List (Almost) All Emojis in Swift for iOS 8 Without Using Any Form of Lookup Tables
How to Import Existing Objective C Classes in Swift
Uitableviewcell Selected Background Color on Multiple Selection
How to Use Mbprogresshud with Swift
Leaving Inputaccessoryview Visible After Keyboard Is Dismissed
Where to Highlight Uicollectionviewcell: Delegate or Cell
Swift: Save Video from Nsurl to User Camera Roll
Add a View on Top of the Keyboard Using Inputaccessoryview
How to Disable Custom Keyboards (Ios8) for My App
Uidatepicker Bug? Uicontroleventvaluechanged After Hitting Minimum Internal
How to Get Previous and Next Month in Calendar-Swift
Is the Function 'Dlopen()' Private API
Easiest Way of Getting Reverse Geocoded Current Location from iOS