package zhidao
import java.util.Arrays
import java.util.LinkedList
public class RecursionSubNSort
{
public static void main ( String[] args )
{
int a = 0
String[] A = { "01", "09", "11", "07", "05", "02" }
String[] B = { "03", "08", "11", "07", "06" }
String bstr = " " + Arrays.toString (B).replaceAll ("[\\[\\],\\s]", ",") + " "
LinkedList<String[]> list = new LinkedList<String[]> ()
recursionSub (list, 1, A, 0, -1)
for ( String[] strings : list )
{
String s = Arrays.toString (strings)
String str = s.replaceAll ("[\\[\\]]", ",")
int i = bstr.split (str).length - 1
a += i
System.out.println (s + " 出现在B中的次数有:" + i)
}
System.out.println ("结果 a = " + a)
System.out.println ("======================================")
list.clear ()
a = 0
recursionSub (list, 2, A, 0, -1)
for ( String[] strings : list )
{
String s = Arrays.toString (strings)
System.out.println ("组合 " + s)
for ( String string : strings )
{
int i = bstr.split ("," + string + ",").length - 1
a += i
System.out.println (string + " 在B中出现的次数有:" + i)
}
}
System.out.println ("结果 a = " + a)
System.out.println ("======================================")
list.clear ()
a = 0
recursionSub (list, 5, A, 0, -1)
for ( String[] strings : list )
{
String s = Arrays.toString (strings)
System.out.println ("组合 " + s)
for ( String string : strings )
{
int i = bstr.split ("," + string + ",").length - 1
a += i
System.out.println (string + " 在B中出现的次数有:" + i)
}
}
System.out.println ("结果 a = " + a)
}
private static LinkedList<String[]> recursionSub ( LinkedList<String[]> list, int count, String[] array, int ind,
int start, int... indexs )
{
start++
if (start > count - 1)
{
return null
}
if (start == 0)
{
indexs = new int[array.length]
}
for ( indexs[start] = ind indexs[start] < array.length indexs[start]++ )
{
recursionSub (list, count, array, indexs[start] + 1, start, indexs)
if (start == count - 1)
{
String[] temp = new String[count]
for ( int i = count - 1 i >= 0 i-- )
{
temp[start - i] = array[indexs[start - i]]
}
list.add (temp)
}
}
return list
}
}
有些人的用复制数列,算法低效、粗野浪费。
给你个、 高效、简洁而且泛型通用的全组合:
public class Test{
public static void main(String[] args) {
String[] a = { "A", "B", "C", "D", "E" }
for(int i=1i<=a.lengthi++){
System.out.println(a.length+"选"+i)
String[] res=new String[i]
combine(a,0,res,0)
}
}
final static public void combine(final Object a[], final int a_pos,final Object rs[], final int rs_pos)
{
if(rs_pos>=rs.length){
for(int i=0i<rs.lengthi++) System.out.print(rs[i]+" ")
System.out.println()
}else for(int ap=a_posap<a.lengthap++){
rs[rs_pos]=a[ap]combine(a,ap+1,rs,rs_pos+1)
}
}
}
=======
5选1
A
B
C
D
E
5选2
A B
A C
A D
A E
B C
B D
B E
C D
C E
D E
5选3
A B C
A B D
A B E
A C D
A C E
A D E
B C D
B C E
B D E
C D E
5选4
A B C D
A B C E
A B D E
A C D E
B C D E
5选5
A B C D E
作者:何史提链接:https://www.zhihu.com/question/22590018/answer/26646688
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
Apriori算法的理念其实很简单,可是实现起上来却复杂无比,因为当中无可避免用Set和Hash Table等高阶的数据结构,而且有很多loop用以读取数据。
我不建议用Java,应改用Python或Scala一类的语言。如果用Python,代码大概50行左右,但可以想像用Java便看起来复杂得多。看如下:
from operator import and_
from itertools import combinations
class AprioriAssociationRule:
def __init__(self, inputfile):
self.transactions = []
self.itemSet = set([])
inf = open(inputfile, 'rb')
for line in inf.readlines():
elements = set(filter(lambda entry: len(entry)>0, line.strip().split(',')))
if len(elements)>0:
self.transactions.append(elements)
for element in elements:
self.itemSet.add(element)
inf.close()
self.toRetItems = {}
self.associationRules = []
def getSupport(self, itemcomb):
if type(itemcomb) != frozenset:
itemcomb = frozenset([itemcomb])
within_transaction = lambda transaction: reduce(and_, [(item in transaction) for item in itemcomb])
count = len(filter(within_transaction, self.transactions))
return float(count)/float(len(self.transactions))
def runApriori(self, minSupport=0.15, minConfidence=0.6):
itemCombSupports = filter(lambda freqpair: freqpair[1]>=minSupport,
map(lambda item: (frozenset([item]), self.getSupport(item)), self.itemSet))
currentLset = set(map(lambda freqpair: freqpair[0], itemCombSupports))
k = 2
while len(currentLset)>0:
currentCset = set([i.union(j) for i in currentLset for j in currentLset if len(i.union(j))==k])
currentItemCombSupports = filter(lambda freqpair: freqpair[1]>=minSupport,
map(lambda item: (item, self.getSupport(item)), currentCset))
currentLset = set(map(lambda freqpair: freqpair[0], currentItemCombSupports))
itemCombSupports.extend(currentItemCombSupports)
k += 1
for key, supportVal in itemCombSupports:
self.toRetItems[key] = supportVal
self.calculateAssociationRules(minConfidence=minConfidence)
def calculateAssociationRules(self, minConfidence=0.6):
for key in self.toRetItems:
subsets = [frozenset(item) for k in range(1, len(key)) for item in combinations(key, k)]
for subset in subsets:
confidence = self.toRetItems[key] / self.toRetItems[subset]
if confidence >minConfidence:
self.associationRules.append([subset, key-subset, confidence])