public List<E> getNElements(List<E> list, Integer n) {
    List<E> rtn = null;

    if (list != null && n != null && n > 0) {
        int lSize = list.size();
        if (lSize > n) {
            rtn = new ArrayList<E>(n);
            E[] es = (E[]) list.toArray();
            //Knuth-Fisher-Yates shuffle algorithm
            for (int i = es.length - 1; i > es.length - n - 1; i--) {
                int iRand = rand.nextInt(i + 1);
                E eRand = es[iRand];
                es[iRand] = es[i];
                //This is not necessary here as we do not really need the final shuffle result.
                //es[i] = eRand;
                rtn.add(eRand);
            }

        } else if (lSize == n) {
            rtn = new ArrayList<E>(n);
            rtn.addAll(list);
        } else {
            log("list.size < nSub! ", lSize, n);
        }
    }

    return rtn;
}

public List<E> getNElementsBitSet(List<E> list, int n) {
        List<E> rtn = new ArrayList<E>(n);
        int[] ids = genNBitSet(n, 0, list.size());
        for (int i = 0; i < ids.length; i++) {
            rtn.add(list.get(ids[i]));
        }
        return rtn;
    }

E[] r = new E[k]; //not really, cannot create an array of generic type, but just pseudo code
int i = 0;
for (E e : list) {
   //assign first k elements:
   if (i < k) { r[i++] = e; continue; }
   //add current element with decreasing probability:
   j = random(i++) + 1; //a number from 1 to i inclusive
   if (j <= k) r[j] = e;
}
return r;

for i = 0 to N-1
    if random(N-i) < k
        add item[i] to the result
        k -= 1
    end
end

Random r = new Random();
Set<Integer> s = new HashSet<Integer>();
for (int j = m - n; j < m; j++) {
    int t = r.nextInt(j);
    s.add(s.contains(t) ? j : t);
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;
import java.util.TreeMap;

public class ReservoirSampling
{
    public static void main(String[] args)
    {
        example();
        //test();
    }

    private static void test()
    {
        List<String> list = new ArrayList<String>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        list.add("E");
        int size = 2;

        int runs = 100000;
        Map<String, Integer> counts = new TreeMap<String, Integer>();
        for (int i=0; i<runs; i++)
        {
            List<String> sample = sample(list, size);
            String s = createString(sample);
            Integer count = counts.get(s);
            if (count == null)
            {
                count = 0;
            }
            counts.put(s, count+1);
        }
        for (Entry<String, Integer> entry : counts.entrySet())
        {
            System.out.println(entry.getKey()+" : "+entry.getValue());
        }
    }

    private static String createString(List<String> list)
    {
        Collections.sort(list);
        StringBuilder sb = new StringBuilder();
        for (String s : list)
        {
            sb.append(s);
        }
        return sb.toString();
    }

    private static void example()
    {
        List<String> list = new ArrayList<String>();
        for (int i=0; i<26; i++)
        {
            list.add(String.valueOf((char)('A'+i)));
        }

        for (int i=1; i<=26; i++)
        {
            printExample(list, i);
        }
    }
    private static <T> void printExample(List<T> list, int size)
    {
        System.out.printf("%3d elements: "+sample(list, size)+"n", size);
    }

    private static final Random random = new Random(0);
    private static <T> List<T> sample(List<T> list, int size)
    {
        List<T> result = new ArrayList<T>(Collections.nCopies(size, (T) null));
        int i = 0;
        for (T element : list)
        {
            if (i < size)
            {
                result.set(i, element);
                i++;
                continue;
            }
            i++;
            int j = random.nextInt(i);
            if (j < size)
            {
                result.set(j, element);
            }
        }
        return result;
    }

}

choose random number from 0 to 99, lets say 42, and add it to result.
choose random number from 0 to 98, lets say 39, and add it to result.
choose random number from 0 to 97, lets say 41, but since 41 is bigger or equal than 39, increment it by 1, so you have 42, but that is bigger then equal than 42, so you have 43.
...

public static <T> List<T> getNRandomElements(int n, List<T> list) {
    List<T> subList = new ArrayList<>(n);
    int[] ids = generateUniformBitmap(n, list.size());
    for (int id : ids) {
        subList.add(list.get(id));
    }
    return subList;
}

// https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2013/08/14/java/UniformDistinct.java
private static int[] generateUniformBitmap(int num, int max) {
    if (num > max) {
        DebugUtil.e("Can't generate n ints");
    }
    int[] ans = new int[num];
    if (num == max) {
        for (int k = 0; k < num; ++k) {
            ans[k] = k;
        }
        return ans;
    }
    BitSet bs = new BitSet(max);
    int cardinality = 0;
    Random random = new Random();
    while (cardinality < num) {
        int v = random.nextInt(max);
        if (!bs.get(v)) {
            bs.set(v);
            cardinality += 1;
        }
    }
    int pos = 0;
    for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
        ans[pos] = i;
        pos += 1;
    }
    return ans;
}

public static <T> List<T> getNRandomShuffledElements(int n, List<T> list) {
    List<T> randomElements = getNRandomElements(n, list);
    Collections.shuffle(randomElements);
    return randomElements;
}