Skip to content

Instantly share code, notes, and snippets.

@isa
Created May 1, 2012 20:10
  • Star 1 You must be signed in to star a gist
  • Fork 17 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save isa/2571012 to your computer and use it in GitHub Desktop.
Convert in less than 30 lines
Question: Convert following into the latter data structure in less than 30 lines:
List:
A, B, C
A, C, E
E, F, D
D, A, J
E, D, J
List
A, B, 1 (frequency)
A, C, 2
A, D, 1
A, E, 1
A, J, 1
B, C, 1
C, E, 1
D, E, 2
D, F, 1
D, J, 2
E, F, 1
E, J, 1
@JoshCheek
Copy link

I don't understand, what are the rules that transform it? e.g. why does A -> C have a frequency of 2, but A -> E has a frequency of 1?

@Serabe
Copy link

Serabe commented May 1, 2012

Done! It was fun. Check my fork!

@JoshCheek: there are two lines that contain an A and a C, but there is only one containing both A and E.

@jdp
Copy link

jdp commented May 1, 2012

Fun thing. Did mine in 3 lines with itertools.

@voidspace
Copy link

A Python one liner:

>>> _ = [__import__('sys').stdout.write('%s %s %s\n' % val) for val  in [(a, b, len([n for n in ['abc', 'ace', 'efd', 'daj', 'edj'] if a in n and b in n])) for a, b in __import__('itertools').combinations('abcdej', 2)]]
a b 1
a c 2
a d 1
a e 1
a j 1
b c 1
b d 0
b e 0
b j 0
c d 0
c e 1
c j 0
d e 2
d j 2
e j 1

@minikomi
Copy link

minikomi commented May 2, 2012

My attempt in clojure: https://gist.github.com/2575554 .. works for groups of any length.

And basically the same thing as a 1 liner (only for groups of 3):

(map #(list (first %) (count (last %))) (sort-by str (group-by identity (reduce concat (map (fn [x] (let [[a b c] x] (list [a b] [a c] [b c])))startinglist)))))

@JoshCheek
Copy link

before = [
  'A', 'B', 'C',
  'A', 'C', 'E',
  'E', 'F', 'D',
  'D', 'A', 'J',
  'E', 'D', 'J',
].each_slice(3).to_a

expected = [
  'A', 'B', 1,
  'A', 'C', 2,
  'A', 'D', 1,
  'A', 'E', 1,
  'A', 'J', 1,
  'B', 'C', 1,
  'C', 'E', 1,
  'D', 'E', 2,
  'D', 'F', 1,
  'D', 'J', 2,
  'E', 'F', 1,
  'E', 'J', 1,
].each_slice(3).to_a


# just counts each pair then formats and sorts it
after = before.each_with_object Hash.new 0 do |chars, all|
  a, b, c = chars.sort
  all[[a, b]] += 1
  all[[a, c]] += 1
  all[[b, c]] += 1
end.map(&:flatten).sort


after == expected # => true

@jabbalaci
Copy link

It's like Apriori. You are looking for 2-long itemsets that occur at least once.

@mauricioszabo
Copy link

1 Line:

list.each_with_object(Hash.new(0)) { |x,o| (x << x[0]).each_cons(2) { |c| o[c.sort] += 1 } }.map { |k,v| k << v }.sort

@mauricioszabo
Copy link

In Scala: https://gist.github.com/2580923
Smaller in scala, but issues an warning: https://gist.github.com/2580938

@peterc
Copy link

peterc commented May 3, 2012

l = [%w{A B C}, %w{A C E}, %w{E F D}, %w{D A J}, %w{E D J}]

p l.map { |a| a.combination(2).map { |b| b.sort.join(' ') } }
  .flatten
  .each_with_object({}) { |a, h| h[a] ||= 0; h[a] += 1 }
  .map { |k, v| [*k.split, v] }
  .sort

@peterc
Copy link

peterc commented May 3, 2012

Shorter, and my last attempt, otherwise I'll be here all night :-) Good fun.

l = [%w{A B C}, %w{A C E}, %w{E F D}, %w{D A J}, %w{E D J}]

v = l.map { |a| [*a.sort.combination(2)] }
    .flatten(1)
    .group_by(&:to_a)
    .map { |h, v| h << v.size }
    .sort

raise unless v == [ ["A", "B", 1], ["A", "C", 2], ["A", "D", 1],
                    ["A", "E", 1], ["A", "J", 1], ["B", "C", 1],
                    ["C", "E", 1], ["D", "E", 2], ["D", "F", 1],
                    ["D", "J", 2], ["E", "F", 1], ["E", "J", 1]]  

@jdp
Copy link

jdp commented May 3, 2012

Could be done in a single expression, but for readability's sake I split into two.

from itertools import chain, imap, combinations, groupby
lines = [['A', 'B', 'C'], ['A', 'C', 'E'], ['E', 'F', 'D'], ['D', 'A', 'J'], ['E', 'D', 'J']]
tuples = map(sorted, chain(*imap(lambda l: combinations(l, 2), lines)))
result = [(k[0], k[1], len(list(g))) for k, g in groupby(sorted(tuples))]

@gregolsen
Copy link

data.each_slice(3).each_with_object(Hash.new(0)) { |x, m| x.combination(2).each { |y| m[y.sort] += 1 } }.sort.flatten

@stehem
Copy link

stehem commented May 4, 2012

I have been doing a lot of Clojure lately :-)

letters = [["A", "B", "C"], ["A", "C", "E"], ["E", "F", "D"], ["D", "A", "J"], ["E", "D", "J"]]

count_combo = lambda do |combo|
letters.reduce(0) { |memo, l| memo += 1 if [combo[0], combo[1]].all? {|k| l.include?(k)}; memo }  
end

letters.reduce([]) {|memo, x| memo << x.map {|l| (x - [l]).map {|m| l+m}}.flatten.reject {|n| n[1] < n[0]}}.flatten.uniq.sort.reduce([]) {|memo, c| memo << [c.split(""), count_combo.call(c)].flatten}

@tjgfernandes
Copy link

hash,list = {},[["A","B","C"],["A","C","E"],["E","F","D"],["D","A","J"],["E","D","J"]]
list.each { |v| (0..1).each {|n| (1..2).each {|i| (n!=i and key=[v[n],v[i]].sort.to_s) ? hash[key] ? hash[key] +=1 : hash[key] = 1 : "" } } }
hash.sort.each {|p| puts "#{p[0][0..0]}, #{p[0][1..1]}, #{p[1]}" }

@manewitz
Copy link

manewitz commented May 7, 2012

Here's my quick first pass at it. That was fun.

inputs, counts, final = [["A", "B", "C"], ["A", "C", "E"], ["E", "F", "D"], ["D", "A", "J"], ["E", "D", "J"]], Hash.new(0), Array.new
inputs.each{|set| set.combination(2).to_a.sort.each{|pair| pair.sort! && counts[pair] += 1}}

# puts'ing a string of the result:

counts.sort.each{ |n| puts "#{n[0][0]}, #{n[0][1]}, #{n[1]}"}

# or just printing the raw data structure
puts
p counts.sort

@akagr
Copy link

akagr commented Mar 2, 2015

5 lines in ruby... although this is general enough to accept arbitrary number of characters per line and any number of lines

res = Hash.new(0)
while a = gets do
    !a.nil? && a.chomp.split(/,\s?/).sort.combination(2).to_a.each {|tuple| res[tuple.join(', ')] += 1}
end
puts res.to_a.map {|tuple| tuple.join(', ')}.sort

@EricDykstra
Copy link

Simple 4 line answer, and in code golf form with a minimum number of characters. Could probably be cut down a bit further, but I didn't spend too much time on it.

h=Hash.new(0)
input.split("\n").map{|a|a.split(", ")}.map{|x|x.combination(2).map{|y|h[y]+=1}}
h.sort_by{|x,y|x[0]}.map{|x,y|puts"#{x[0]}, #{x[1]}, #{y}"}
puts h

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment