<div dir="ltr"><a href="https://wiki.haskell.org/99_questions/Solutions/26">https://wiki.haskell.org/99_questions/Solutions/26</a><br></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature">:: atomly ::<br><br>[ <a href="mailto:atomly@atomly.com" target="_blank">atomly@atomly.com</a> : <a href="http://www.atomly.com" target="_blank">www.atomly.com</a>  : <a href="http://blog.atomly.com/" target="_blank">http://blog.atomly.com/</a> ...<br>[ atomiq records : new york city : +1.347.692.8661 ...<br>[ e-mail <a href="mailto:atomly-news-subscribe@atomly.com" target="_blank">atomly-news-subscribe@atomly.com</a> for atomly info and updates ...</div></div>
<br><div class="gmail_quote">On Sun, Apr 10, 2016 at 11:59 AM, rohan sumant <span dir="ltr"><<a href="mailto:r.s.sumant@gmail.com" target="_blank">r.s.sumant@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Suppose I have a list of distinct integers and I wish to generate all possible unordered pairs (a,b) where a/=b.<div><br></div><div>Ex: [1,2,3,0] --> [(1,2),(1,3),(1,0),(2,3),(2,0),(3,0)]</div><div><br></div><div> The approach I am following is this :-<div><br></div><div>mkpairs [] = []<br></div><div>mkpairs (x:xs) = (map (fn x) xs) ++ (mkpairs xs)</div><div><div><div><div dir="ltr"><div><br></div><div>fn x y = (x,y)</div><div><br></div><div>It is generating the desired output but I am a bit unsure about the time complexity of the function mkpairs. In an imperative language a nested triangular for loop would do the trick in O(n^2) or more precisely (n*(n-1)/2) operations. Does my code follow the same strategy? I am particularly worried about the (++) operator. I think that (++) wouldn't add to the time complexity since the initial code fragment (map (fn x) xs) is to be computed anyway. Am I wrong here? Is this implementation running O(n^2)? If not, could you please show me how to write a nested triangular loop in Haskell?<span class="HOEnZb"><font color="#888888"><br><br>Rohan Sumant<br>    </font></span></div></div></div></div>
</div></div></div>
<br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div>